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;

class Main {

    public static void main(String[] args) {
    	try (Scanner sc = new Scanner(System.in)){
			int n = sc.nextInt();
			String target = "";
			for (int i = 0; i < n; i++) {
				target += sc.nextInt();
				if (i != n-1) target += " ";  //空白を入れる
			}
			String a = "";
			for (int i=1; i<n+1; i++) a += i;
			List<String> list = new ArrayList<String>();
			list = permutation(list,a,"");

			//結果出力---------------------------------------------------
			int index = -1;
			for (int i = 0; i < list.size(); i++) {
				if (list.get(i).equals(target)){
					index = i;
					break;
				}
			}
 			if (index != 0) System.out.println(list.get(index - 1));  //前の順列が存在したら出力する
 			System.out.println(list.get(index));  //与えられた数列を出力する
 			if (index != list.size()-1) System.out.println(list.get(index + 1));  //次の順列が存在したら出力する
    	}
  }

    static List<String> permutation( List<String> list,String input, String ans){
    	//1まで削ったらその回を終了して、答えをListに入れる
    	if (input.length() <= 1) {
    		list.add(ans + input);  //最後の数字はここでくっつく
    	} else {
    		for (int i=0; i<input.length(); i++) {  //inputの1、2、3…char目を分離して、残りの方に挿入する
    			permutation(list ,input.substring(0, i) + input.substring(i + 1), ans + input.charAt(i) + " "); //空白を入れる
    		}
    	}
    	return list;
    }
}