描述

输入一个正整数\(n\)，输出它的全排列。

格式

输入格式

一行，一个正整数\(n\)。

\(1\leq n\leq 9\)

输出格式

若干行，\(n\)的全排列。

样例

输入样例

4

输出样例

1234
1243
1324
1342
1423
1432
2134
2143
2314
2341
2413
2431
3124
3142
3214
3241
3412
3421
4123
4132
4213
4231
4312
4321

限制

内存256MB，时间1s。

小心TLE哦！