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;
using lint = long long;
template<typename T = lint>inline T in() { T x; cin >> x; return x; }
#define INF           1e9
#define INFL          static_cast<lint>(INF)
#define REP(i,n)      for(lint i=0,i##_len=(n);i<i##_len;++i)
#define REP1(i,n)     for(lint i=1,i##_len=(n);i<=i##_len;++i)
#define REPR(i,n)     for(lint i=n-1;i>=0;--i)
#define REPR1(i,n)    for(lint i=n;i>0;--i)
#define REPI(i,ini,n) for(lint i=(ini),i##_len=(n);i<i##_len;++i)
#define REPC(i,obj)   for(auto i:obj)
#define R_UP(a,b)     (((a)+(b)-1)/(b))
#define ALL(obj)      (obj).begin(),(obj).end()
int main()
{
	int n = in();
	vector<int>a(n);
	REPC(&i, a)i = in();
	int index = -1;
	REPR(i, n - 1)
	{
		if (a[i] > a[i + 1])
		{
			index = i;
			break;
		}
	}
	if (index != -1)
	{
		REP(i, index)cout << a[i] << ' ';
		vector<int>a_copy(a.begin() + index, a.end());
		vector<int>::iterator itr;
		for (int i = 1;; ++i)if ((itr = find(ALL(a_copy), a[index] - i)) != a_copy.end())break;
		cout << *itr << ' ';
		a_copy.erase(itr);
		sort(ALL(a_copy), greater<int>());
		REP(i, a_copy.size())
		{
			if (i != 0)cout << ' ';
			cout << a_copy[i];
		}
		cout << endl;
	}
	REP(i, a.size())
	{
		if (i != 0)cout << ' ';
		cout << a[i];
	}
	cout << endl;
	index = -1;
	REPR(i, n - 1)
	{
		if (a[i] < a[i + 1])
		{
			index = i;
			break;
		}
	}
	if (index != -1)
	{
		REP(i, index)cout << a[i] << ' ';
		vector<int>a_copy(a.begin() + index, a.end());
		vector<int>::iterator itr;
		for (int i = 1;; ++i)if ((itr = find(ALL(a_copy), a[index] + i)) != a_copy.end())break;
		cout << *itr << ' ';
		a_copy.erase(itr);
		sort(ALL(a_copy));
		REP(i, a_copy.size())
		{
			if (i != 0)cout << ' ';
			cout << a_copy[i];
		}
		cout << endl;
	}
}