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;
typedef long long ll;

// #define DEBUG

vector<string> perm_enum(string s, int n)
{
    vector<string> a;
    string t;
    if (n == 1)
    {
        a.push_back(s);
        return a;
    }
    else
    {
        for (int i = 0; i < n; i++)
        {
            t = "";
            for (int j = 0; j < n; j++)
            {
                if (i != j)
                    t += s[j];
            }
            vector<string> b = perm_enum(t, n - 1);
            for (string r : b)
                a.push_back(s[i] + r);
        }

        return a;
    }
}

int main()
{

#ifdef DEBUG
    cout << "DEBUG MODE" << endl;
    ifstream in("input.txt"); //for debug
    cin.rdbuf(in.rdbuf());    //for debug
#endif
    int n;
    cin >> n;
    string t;
    for (int i = 0; i < n; i++)
        t += i + '1';
    vector<string> ans = perm_enum(t, n);
    for (string s : ans)
    {
        for (int i = 0; i < n - 1; i++)
            cout << s[i] << " ";
        cout << s[n - 1] << "\n";
    }

    return 0;
}
