Description

给出n，按顺序输出n的全排列。n<=10

Format

Input

一个整数n

Output

每行一个排列。

Samples

3

123
132
213
231
312
321

Limitation

1s, 1024KiB for each test case.