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;

void output(vector<int> v) {
  int n = v.size();

  for (int i = 0; i < n; i++) {
    if (i)
      cout << " ";
    cout << v[i];
  }
  cout << endl;
}

vector<int>::reverse_iterator next_element(int ref, vector<int>::reverse_iterator begin,
                                           vector<int>::reverse_iterator end) {
  int min=1000000;
  auto next_itr = begin;
  for (auto itr = begin; itr != end; itr++) {
    if (*itr > ref && *itr < min) {
      min = *itr;
      next_itr = itr;
    }
  }
  return next_itr;
}

vector<int>::reverse_iterator prev_element(int ref, vector<int>::reverse_iterator begin,
                                           vector<int>::reverse_iterator end) {
  int max = 0;
  auto prev_itr = begin;
  for (auto itr = begin; itr != end; itr++) {
    if (*itr<ref&& * itr> max) {
      max = *itr;
      prev_itr = itr;
    }
  }
  return prev_itr;
}

bool next_permutation(vector<int>& pv) {
  for (auto itr = pv.rbegin(); next(itr, 1) != pv.rend(); itr++) {
    if (*next(itr, 1) < *itr) {
      iter_swap(next_element(*next(itr), pv.rbegin(), next(itr)), next(itr, 1));
      sort(pv.rbegin(), next(itr), greater<int>());
      return 1;
    }
  }
  return 0;
}

bool prev_permutation(vector<int>& pv) {
  for (auto itr = pv.rbegin(); next(itr, 1) != pv.rend(); itr++) {
    if (*next(itr, 1) > *itr) {
      iter_swap(prev_element(*next(itr), pv.rbegin(), next(itr)), next(itr, 1));
      sort(pv.rbegin(), next(itr), less<int>());
      return 1;
    }
  }
  return 0;
}

int main() {
  ios::sync_with_stdio(false);

  int n;
  cin >> n;

  vector<int> pv(n), v(n), nv(n);

  for (int i = 0; i < n; i++) {
    cin >> v[i];
  }

  pv = v;
  if (prev_permutation(pv) == true) {
    output(pv);
  }

  output(v);
  nv = v;
  if (next_permutation(nv) == true) {
    output(nv);
  }

  return 0;
}