#include <stdio.h>
#include <stdlib.h>

void sort_vector(int n, int *v, int starting) {
	int i, j, tmp;
	for (i = starting ; i < n - 1 ; ++i) {
		for (j = i + 1 ; j < n ; ++j) {
			if (v[i] > v[j]) {
				tmp = v[i];
				v[i] = v[j];
				v[j] = tmp;
			}
		}
	}
}

int next_permutation(int n, int *v) {
	int i, pivot = -1, minim = 9, position;
	// Gasim ultima inversiune
	for (i = 0 ; i < n - 1 ; ++i) {
		if (v[i] < v[i + 1]) {
			pivot = i;
		}
	}
	if (pivot == -1) {
		return 0;
	}
	// Cautam minimul, dintre elementele ramase, mai mare decat pivotul
	for (i = pivot + 1 ; i < n ; ++i) {
		if (v[i] > v[pivot] && v[i] < minim) {
			minim = v[i];
			position = i;
		}
	}
	// Swapping
	int tmp = v[pivot];
	v[pivot] = v[position];
	v[position] = tmp;
	// Sortam ce a ramas
	sort_vector(n, v, pivot + 1);
	return 1;
}

int main() {
	int n;
	FILE* in = fopen("permutari.in", "rt");
	if (in == NULL) {
		printf("Nu am putut deschide fisierul de input!\n");
		return -1;
	}
	FILE* out = fopen("permutari.out", "wt");
	if (out == NULL) {
		printf("Nu am putut deschide fisierul de output!\n");
		return -2;
	}
	// Citire variabile
	fscanf(in, "%d", &n);
	int *v = malloc(n * sizeof(int));
	for (int i = 0 ; i < n ; ++i) {
		v[i] = i + 1;
	}
	sort_vector(n, v, 0);
	for (int i = 0 ; i < n ; ++i) {
		fprintf(out, "%d ", v[i]);
	}
	fprintf(out, "\n");
	while (next_permutation(n, v)) {
		for (int i = 0 ; i < n ; ++i) {
			fprintf(out, "%d ", v[i]);
		}
		fprintf(out, "\n");
	}
	// Free the memory
	fclose(in);
	fclose(out);
	free(v);
	return 0;
}