자연수 N이 주어졌을 때, 1부터 N까지의 자연수 중에서 중복 없이 N개를 고른 수열을 모두 구하는 프로그램을 작성하시오.

이는 1부터 N까지의 숫자를 일렬로 나열하는 모든 순열(Permutation)을 구하는 것과 같습니다.

입력

첫째 줄에 자연수 N이 주어진다.

출력

첫째 줄부터 N!개의 줄에 걸쳐 한 줄에 하나씩 수열을 출력한다. 공백으로 구분해서 출력해야 하며, 사전 순으로 앞서는 수열부터 오름차순으로 출력해야 한다.

제한 사항

• 1 ≤ N ≤ 8

예제 입력 1

3

예제 출력 1

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

예제 입력 2

2

예제 출력 2

1 2
2 1