Problem: For given a sequence $A = \\{a_0, a_1, ..., a_{n-1}\\}$, print the previous permutation and the next permutation in lexicographic order.

Constraints

* $1 \leq n \leq 9$
* $a_i$ consist of $1, 2, ..., n$

Input

A sequence is given in the following format.


$n$
$a_0 \; a_1 \; ... \; a_{n-1}$


Output

Print the previous permutation, the given sequence and the next permutation in the 1st, 2nd and 3rd lines respectively. Separate adjacency elements by a space character. Note that if there is no permutation, print nothing in the corresponding line.

Examples

Input

3
2 1 3


Output

1 3 2
2 1 3
2 3 1


Input

3
3 2 1


Output

3 1 2
3 2 1

Solution (in CPP):

Solution:
#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){
    cin >> nums[i];
  }

  // 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;
  }
}