Description

给定一个整数n，1 ~ n每个数字有很多种排列方式。请你按照字典序把他们全部打印出来。

Format

Input

一个正整数n。

Output

输出若干行，每行按照字典序输出

Samples

3

123
132
213
231
312
321

Limitation

n<=5