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:
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP2_5_C&lang=jp
#  Enumeration : python3
#  2018.12.01 yonezawa

import sys
input = sys.stdin.readline
from collections import deque

class enumeration:
    def __init__(self,n):
        self.n = n
        self.depth = 0
        self.wnum = 0
        self.nq = []
        self.bits = [ pow(2,i) for i in range(n+1) ]
        self.mk_permutation(0,0,0)

    def mk_permutation(self,depth,bflag,wnum):
        if self.n == depth:
            self.nq.append(wnum)
            return
        for i in range(1,self.n+1):
            if bflag & self.bits[i-1] != 0:
                continue
            self.mk_permutation(depth + 1,bflag + self.bits[i-1],wnum*10+i)  
            
    def printList(self):
        l = self.nq
        self.nq.sort()
        for i in l:
            self.printInttoStr(i)
            
    def printInttoStr(self,i):
        c = ""
        for j in str(i):
            c += j + " "
        print(c.strip())

    def solve(self,tc):
        pos = self.nq.index(tc)
        if (pos != 0 ):
            self.printInttoStr(self.nq[pos-1])
        self.printInttoStr(tc)
        if (pos + 1 != len(self.nq) ):
            self.printInttoStr(self.nq[pos+1])
            
def main():
    n = int(input())
    tc = 0
    for i in list(map(int,input().split())):
        tc = tc * 10 + i
    e = enumeration(n)
    e.solve(tc)

if __name__ == '__main__':
    main()