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 <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
	int n;
	cin >> n;
	vector<int> given(n);	// the given sequence
	vector<int> prev(n);	// the previous permutation
	vector<int> next(n);	// the next permutation
	for_each(given.begin(),given.end(),[](int &_e){cin >> _e;});
	prev.assign(given.begin(),given.end());
	next.assign(given.begin(),given.end());
	if (prev_permutation(prev.begin(),prev.end())) {
		int i = 1;
		for_each(prev.begin(),prev.end(),[&i,n](int _e){cout << _e << (i++ == n ? "\n" : " ");});
	}
	int j = 1;
	for_each(given.begin(),given.end(),[&j,n](int _e){cout << _e << (j++ == n ? "\n" : " ");});
	if (next_permutation(next.begin(),next.end())) {
		int i = 1;
		for_each(next.begin(),next.end(),[&i,n](int _e){cout << _e << (i++ == n ? "\n" : " ");});
	}
}