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>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


int N;
int table_index;
int table[362880][9];
int tmp_array[9];
bool used[10];
map<ll,int> MAP;

void recursive(int index){

	if(index == N){

		ll num = 0;

		for(int i = 0; i < N; i++){
			table[table_index][i] = tmp_array[i];
			num = 10*num+tmp_array[i];
		}

		MAP[num] = table_index++;
		return;
	}

	for(int i = 1; i <= N; i++){

		if(used[i])continue;
		tmp_array[index] = i;
		used[i] = true;
		recursive(index+1);
		used[i] = false;
	}
}

void output(int index){

	printf("%d",table[index][0]);
	for(int i = 1; i < N; i++){
		printf(" %d",table[index][i]);
	}
	printf("\n");
}


int main(){

	scanf("%d",&N);

	int tmp;

	if(N == 1){

		scanf("%d",&tmp);

		printf("1\n");
		return 0;
	}

	table_index = 0;

	for(int i = 1; i <= N; i++)used[i] = false;

	for(int i = 1; i <= N; i++){

		tmp_array[0] = i;
		used[i] = true;
		recursive(1);

		used[i] = false;
	}

	ll num = 0;
	for(int i = 0; i < N; i++){
		scanf("%d",&tmp);
		num = 10*num+tmp;
	}

	int index = MAP[num];

	if(index > 0){
		output(index-1);
	}
	output(index);
	if(index < table_index-1){
		output(index+1);
	}

	return 0;
}