Background

土拨鼠进监狱了，他需要写出n的全排列才能出狱。

Description

给出n，输出n的全排列。

Format

Input

一行，一个数n

Output

$n!$行，每行是n的一个全排列，按字典序输出。

Samples

3

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

Limitation

1秒，256mb。$n<=8$