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:
# AOJ ITP2_5_C: Permutation
# Python3 2018.6.24 bal4u

def next_permutation(a):
    # if list has less than two elements, has no next permutation.
    if len(a) < 2: return False

    # step 1: find max i for a[i] > a[i+1]
    i = len(a)-2
    while i >= 0 and a[i] >= a[i+1]: i -= 1
    if i < 0: return False
    j = i + 1

    # step 2: find max k for a[k] > a[i]
    k = len(a) - 1
    while a[i] >= a[k]: k -= 1

    # step 3: swap a[i] and a[k]
    (a[i], a[k]) = (a[k], a[i])

    # step 4: reverse a[j:]
    a[j:] = a[:j-1:-1]

    return True

def prev_permutation(a):
    # if list has less than two elements, has no prev permutation.
    if len(a) < 2: return False

    # step 1: find max i for a[i] < a[i+1]
    i = len(a)-2
    while i >= 0 and a[i] <= a[i+1]: i -= 1
    if i < 0: return False
    j = i + 1

    # step 2: find max k for a[k] < a[i]
    k = len(a) - 1
    while a[i] <= a[k]: k -= 1

    # step 3: swap a[i] and a[k]
    (a[i], a[k]) = (a[k], a[i])

    # step 4: reverse a[j:]
    a[j:] = a[:j-1:-1]

    return True
            
n = int(input())
a = list(map(int, input().split()))
n, p = list(a), list(a)
if prev_permutation(p): print(*p)
print(*a)
if next_permutation(n): print(*n)