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;
#define rep_i(i, n) for (int i = 0; i < (n); ++i)
#define rep_ll(i, n) for (long long i = 0; i < (n); ++i)
#define r_rep_i(i, start, end) for (int i = (start); i < (end); ++i)
#define r_rep_ll(i, start, end) for (long long i = (start); i < (end); ++i)
#define debug_vi(v) copy((v).begin(), (v).end(), ostream_iterator<int>(cout, " "));
#define debug_vll(v) copy((v).begin(), (v).end(), ostream_iterator<long long>(cout, " "));
#define debug_vd(v) copy((v).begin(), (v).end(), ostream_iterator<double>(cout, " "));
#define sort_v(v) sort((v).begin(), (v).end()); //昇順
#define d_sort_vi(v) sort((v).begin(), (v).end(), greater<int>()); //降
#define d_sort_vd(v) sort((v).begin(), (v).end(), greater<double>()); //昇順
#define say(t) cout << (t) << endl;
#define sum_vi(v) accumulate((v).begin(), (v).end(), 0);
#define sum_vll(v)accumulate((v).begin(), (v).end(), 0LL);

int main(){
  int n;cin >> n;
  vector<int> nums(n);
  rep_i(i, n){
    nums[i] = i + 1;
  }

  do {
    for (vector<int>::iterator i = nums.begin(); i != nums.end(); i++)
    {
      if(i == nums.begin()){
        cout << *i;
        continue;
      }
      cout << " " << *i;
    }
    cout << endl;
  }while(next_permutation(nums.begin(), nums.end()));

  // if(prev_permutation(nums.begin(), nums.end())){
  //   for (vector<int>::iterator i = nums.begin(); i != nums.end(); i++)
  //   {
  //     if(i == nums.begin()){
  //       cout << *i;
  //       continue;
  //     }
  //     cout << " " << *i;
  //   }
  //   cout << endl;
  // }
  // next_permutation(nums.begin(), nums.end());
  // for (vector<int>::iterator i = nums.begin(); i != nums.end(); i++)
  // {
  //   if(i == nums.begin()){
  //     cout << *i;
  //     continue;
  //   }
  //   cout << " " << *i;
  // }
  // cout << endl;
  // if(next_permutation(nums.begin(), nums.end())){
  //   for (vector<int>::iterator i = nums.begin(); i != nums.end(); i++)
  //   {
  //     if(i == nums.begin()){
  //       cout << *i;
  //       continue;
  //     }
  //     cout << " " << *i;
  //   }
  //   cout << endl;
  // }
}
