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 JAVA):

Solution:
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();

		String numberArray1 = "";  //1～n-1の数字が順に格納された数列リスト
		String numberArray2 = "";  //比較する数列リスト

		for(int i = 1; i <= n; i++) {
			numberArray1 += String.valueOf(i);
			numberArray2 += String.valueOf(sc.nextInt());
		}

		List<String> numberList = new ArrayList<String>();
		permutation(numberArray1, "", numberList);

		for(int i = 0; i < numberList.size(); i++) {
			if(numberList.get(i).equals(numberArray2)) {
				if(i != 0) display(numberList.get(i-1));
				display(numberArray2);
				if(i != numberList.size() - 1) display(numberList.get(i+1));
				break;
			}
		}
	}

	public static List<String> permutation(String s, String ans, List<String> list) {
		if(s.length() <= 1) {
			list.add(ans + s);
		}
		else {
			for(int i = 0; i < s.length(); i++) {
				permutation(s.substring(0, i) + s.substring(i + 1), ans + s.charAt(i), list);
			}
		}

		return list;
	}

	//String型を引数としそれを空白を開けて表示するメソッド
	public static void display(String s) {
		for(int i = 0; i < s.length(); i++) {
			if(i != 0) System.out.print(" ");
			System.out.print(s.charAt(i));
		}
		System.out.println();
	}

}