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:
def next_permutation(a):
    # if list has less than two elements, has no next permutation
    if len(a) < 2:
        return False

    # step1 : 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

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

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

    # step4 : 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

    # step1 : 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

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

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

    # step4 : 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)