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

#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define ALL(v) (v).begin(), (v).end()

ostream& operator<<(ostream& o, vector<ll> &A){
    FOR(i, 0, A.size()){
        if(i){
            o << ' ';
        }
        o << A[i];
    }
    o << endl;
    return o;
}

int main(){
    ll N;
    cin >> N;

    vector<ll> A;
    FOR(i, 0, N){
        A.push_back(i+1);
    }

    do{
        cout << A;
    }while(next_permutation(ALL(A)));

    return 0;
}
