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 <iostream>
#include <vector>
using namespace std;

int n;
int fact[10];
int used[10] = {0};
int A[10];
vector<int> v;
vector<int> num = {1,2,3,4,5,6,7,8,9};

void permutation(int n,int i){
	int c = n,t = i;
	for(int j=0;j<n;j++){
		if(c>0){
			v.push_back(num[t/fact[c-1]]);
			num.erase(num.begin()+t/fact[c-1]);
			t -= (t/fact[c-1])*fact[c-1];
			c--;
		}else{
			v.push_back(num[0]);
		}
	}
	num.clear();
	for(int j=0;j<n;j++){
		if(j!=n-1) cout << v[j] << " ";
		else cout << v[j] << endl;
		used[j] = 0;
		num.push_back(j+1);
	}
	v.clear();
}

int main(){
	cin >> n;
	for(int i=0;i<n;i++) cin >> A[i];
	for(int i=0;i<=n;i++){
		if(i==0) fact[i] = 1;
		else fact[i] = fact[i-1]*i;
	}
	int ord = 0,now = n-1;
	for(int i=0;i<n;i++){
		ord += fact[now]*(A[i]-1);
		for(int j=i+1;j<n;j++){
			if(A[j]>A[i]) A[j]--;
		}
		now--;
	}
	if(ord-1>=0) permutation(n,ord-1);
	permutation(n,ord);
	if(ord+1<fact[n]) permutation(n,ord+1);
}