题目描述

现在有一个栈，有 $n$ 个元素，分别为 $1,2,…,n$。我们可以通过 push 和 pop 操作，将这 $n$ 个元素依次放入栈中，然后从栈中弹出，依次把出栈的元素写下来得到的序列就是出栈序列。

比如 $n=3$，如果执行 push 1, push 2, pop, push 3, pop, pop，那么我们 pop 操作得到的元素依次是 $2,3,1$。也就是说出栈序列就是 $2,3,1$。

请按字典序从小到大的顺序输出所有的 $n$ 个元素的可行的出栈序列。

输入格式

一行一个整数 $n$。

输出格式

按字典序从小到大的顺序一行一行输出所有的 $n$ 个元素的可行的出栈序列，每行一个序列，相邻两个数字需要用空格隔开。

3

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

数据规模

对于 100% 的数据，保证 $1≤n≤12$。