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

Solution:
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001


N = int(input())

table = [None] * N
check = [False] * (N+1)
MAP = {}
rev_MAP = {}
perm_index = 0


def recursive(index):
    global perm_index
    if index == N:
        tmp = 0
        for i in range(N):
            tmp = 10*tmp+table[i]

        MAP[perm_index] = tmp
        rev_MAP[tmp] = perm_index
        perm_index += 1
        return

    for i in range(1,(N+1)):
        if check[i]:
            continue
        check[i] = True
        table[index] = i
        recursive(index+1)
        check[i] = False


def outPut(num):
    S = deque()
    while True:
        S.appendleft(num%10)
        num //= 10
        if num == 0:
            break
    print("%d"%(S.popleft()),end="")
    while len(S) > 0:
        print(" %d"%(S.popleft()),end="")
    print()



recursive(0)

tmp = 0

for i in list(map(int,input().split())):
    tmp = 10*tmp+i

index = rev_MAP[tmp]
if index > 0:
    outPut(MAP[index-1])

outPut(tmp)

if index+1 in MAP:
    outPut(MAP[index+1])