For given an integer $n$, print all permutations of $\\{1, 2, ..., n\\}$ in lexicographic order.

Constraints

* $1 \leq n \leq 9$

Input

An integer $n$ is given in a line.

Output

Print each permutation in a line in order. Separate adjacency elements by a space character.

Examples

Input

2


Output

1 2
2 1


Input

3


Output

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
#include<bits/stdc++.h>
using namespace std;
using lint = long long;
template<typename T = lint>inline T in() { T x; cin >> x; return x; }
#define INF           1e9
#define INFL          static_cast<lint>(INF)
#define REP(i,n)      for(lint i=0,i##_len=(n);i<i##_len;++i)
#define REP1(i,n)     for(lint i=1,i##_len=(n);i<=i##_len;++i)
#define REPR(i,n)     for(lint i=n-1;i>=0;--i)
#define REPR1(i,n)    for(lint i=n;i>0;--i)
#define REPI(i,ini,n) for(lint i=(ini),i##_len=(n);i<i##_len;++i)
#define REPC(i,obj)   for(auto i:obj)
#define R_UP(a,b)     (((a)+(b)-1)/(b))
#define ALL(obj)      (obj).begin(),(obj).end()
int main()
{
	int n = in();
	vector<int>a(n);
	REP(i, n)a[i] = i + 1;
	REP(i, a.size())
	{
		if (i != 0)cout << ' ';
		cout << a[i];
	}
	cout << endl;
	while (true)
	{
		int index = -1;
		REPR(i, n - 1)
		{
			if (a[i] < a[i + 1])
			{
				index = i;
				break;
			}
		}
		if (index != -1)
		{
			REP(i, index)cout << a[i] << ' ';
			vector<int>a_copy(a.begin() + index, a.end());
			vector<int>::iterator itr;
			for (int i = 1;; ++i)if ((itr = find(ALL(a_copy), a[index] + i)) != a_copy.end())break;
			cout << *itr << ' ';
			a[index] = *itr;
			a_copy.erase(itr);
			sort(ALL(a_copy));
			REP(i, a_copy.size())
			{
				if (i != 0)cout << ' ';
				cout << a_copy[i];
				a[index + 1 + i] = a_copy[i];
			}
			cout << endl;
		}
		else break;
	}
}
