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

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
import operator

def permutations(li):

	def perm(op):

		def func(xs):
			i = len(xs) - 1
			while i > 0 and op(xs[i - 1], xs[i]):
				i -= 1
			if i > 0:
				i -= 1
				j = i + 1
				while j < len(xs) and op(xs[j], xs[i]):
					j += 1
				(xs[i], xs[j - 1]) = (xs[j - 1], xs[i])
				return xs[:i + 1] + list(reversed(xs[i + 1:]))
			else:
				return None
		return func
	prev_perm = perm(operator.lt)
	next_perm = perm(operator.gt)
	ps = []
	pp = prev_perm(li[:])
	if pp is not None:
		ps.append(pp)
	ps.append(li[:])
	np = next_perm(li[:])
	if np is not None:
		ps.append(np)
	return ps

def run():
	n = int(input())
	li = [int(x) for x in input().split()]
	assert n == len(li)
	for ps in permutations(li):
		print(' '.join([str(x) for x in ps]))
run()


from itertools import permutations

def main():
	n = int(input())
	a = [int(x) for x in input().split()]
	perm = list(permutations(sorted(a)))
	for i in range(len(perm)):
		if a == list(perm[i]):
			if 0 < i:
				print(' '.join(map(str, perm[i - 1])))
			print(' '.join(map(str, perm[i])))
			if i < len(perm) - 1:
				print(' '.join(map(str, perm[i + 1])))
main()


import os
import sys
from itertools import permutations as nPr
from copy import deepcopy

def main():
	n = int(input())
	a = list(map(int, input().split()))
	s = sorted(deepcopy(a))
	p = list(nPr(s))
	inde = p.index(tuple(a))
	if inde != 0:
		print(p[inde - 1][0], end='')
		for i in range(1, n):
			print(' {}'.format(p[inde - 1][i]), end='')
		print()
	print(p[inde][0], end='')
	for i in range(1, n):
		print(' {}'.format(p[inde][i]), end='')
	print()
	if inde != len(p) - 1:
		print(p[inde + 1][0], end='')
		for i in range(1, n):
			print(' {}'.format(p[inde + 1][i]), end='')
		print()
main()


from itertools import permutations
n = int(input())
a = tuple(map(int, input().split()))
p = list(permutations(sorted(a), n))
for i in p:
	if a == i:
		j = p.index(i)
		if j != 0:
			print(*p[j - 1])
		print(*i)
		if j + 1 < len(p):
			print(*p[j + 1])


def rec(lst, d):
	for i in range(1, len(lst) + 1):
		if i not in lst:
			lst[d] = i
			if d + 1 == len(lst):
				a = list(lst)
				P.append(a)
				lst[d] = 0
				return
			else:
				rec(lst, d + 1)
				lst[d] = 0
N = int(input())
S = list(map(int, input().split()))
P = []
lst = []
for i in range(N):
	lst.append(0)
rec(lst, 0)
for i in range(len(P)):
	if S == P[i]:
		if i != 0:
			print(*P[i - 1])
		print(*P[i])
		if i + 1 != len(P):
			print(*P[i + 1])


from itertools import permutations
n = int(input())
a = list(map(int, input().split()))
b = list(permutations(range(1, n + 1)))
for i in range(len(b)):
	if b[i] == tuple(a):
		if i == 0:
			pass
		else:
			print(' '.join(map(str, b[i - 1])))
		print(' '.join(map(str, a)))
		if i == len(b) - 1:
			pass
		else:
			print(' '.join(map(str, b[i + 1])))
		break


from itertools import permutations
n = int(input())
p = list(permutations([str(x) for x in range(1, n + 1)], n))
arr = tuple(input().split())
idx = p.index(arr)
[print(' '.join(p[idx + i])) for i in range(-1, 2) if 0 <= idx + i < len(p)]


from itertools import permutations
input()
A = tuple(map(int, input().split()))
p = sorted(list(permutations(A)))
index = p.index(A)
if index > 0:
	print(*p[index - 1])
print(*A)
if index < len(p) - 1:
	print(*p[index + 1])


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 = 1e-09
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])


import itertools
from typing import List, Tuple

def print_elems(elems):
	print(' '.join([str(elem) for elem in elems]))
n = int(input())
nums = tuple(map(lambda x: int(x), input().split()))
nums_permutated = list(itertools.permutations(sorted(nums)))
if 1 == len(nums_permutated):
	print(nums[0])
	exit(0)
for idx in range(1, len(nums_permutated)):
	if nums == nums_permutated[idx - 1]:
		print_elems(nums_permutated[idx - 1])
		print_elems(nums_permutated[idx])
		exit(0)
	if nums == nums_permutated[idx]:
		print_elems(nums_permutated[idx - 1])
		print_elems(nums_permutated[idx])
		if idx != len(nums_permutated) - 1:
			print_elems(nums_permutated[idx + 1])
		exit(0)


import sys
import itertools
n = int(sys.stdin.readline())
a = tuple(map(int, sys.stdin.readline().split()))
prev = ()
for l in itertools.permutations(sorted(a), n):
	if a == l:
		if len(prev) > 0:
			print(' '.join(map(str, prev)))
		print(' '.join(map(str, a)))
	if prev == a:
		print(' '.join(map(str, l)))
	prev = l


from itertools import permutations
n = int(input())
A = tuple(input().split())
str_num = ''
for num in range(1, n + 1):
	str_num += str(num)
flag_break = False
list_num_previous = None
for list_num in permutations(str_num):
	if flag_break:
		print(*list_num)
		break
	if list_num == A:
		if list_num_previous != None:
			print(*list_num_previous)
		print(*list_num)
		flag_break = True
	list_num_previous = list_num


import itertools
n = input()
a = tuple(map(int, input().split()))
p = sorted(list(itertools.permutations(a)))
i = p.index(a)
if i > 0:
	print(*p[i - 1])
print(*p[i])
if i < len(p) - 1:
	print(*p[i + 1])


import itertools
n = int(input())
num = list(map(int, input().split()))
per = list(itertools.permutations(num))
per.sort()
index = per.index(tuple(num))
if index != 0:
	print(' '.join((str(n) for n in per[index - 1])))
print(' '.join((str(n) for n in per[index])))
if index != len(per) - 1:
	print(' '.join((str(n) for n in per[index + 1])))


from itertools import permutations
n = int(input())
A = tuple(map(int, input().split()))
res = [p for p in permutations(sorted(A), n)]
i = res.index(A)
for a in res[max(0, i - 1):i + 2]:
	print(*a)


import itertools
n = int(input())
a = input()
b = range(1, n + 1)
prev = ''
ans1 = ''
ans2 = ''
flag = False
for x in itertools.permutations(b):
	y = ' '.join(list(map(str, x)))
	if flag:
		ans2 = y
		break
	if a == y:
		ans1 = prev
		flag = True
	prev = y
if ans1 != '':
	print(ans1)
print(a)
if ans2 != '':
	print(ans2)


import itertools
n = int(input())
a = [int(i) for i in input().split(' ')]
perms = list(itertools.permutations([i + 1 for i in range(n)]))
for (i, p) in enumerate(perms):
	if list(p) == a:
		break
if i > 0:
	print(' '.join([str(j) for j in perms[i - 1]]))
print(' '.join([str(j) for j in perms[i]]))
try:
	print(' '.join([str(j) for j in perms[i + 1]]))
except IndexError:
	pass


from itertools import permutations
n = int(input())
a = tuple(map(int, input().split()))
p = [i for i in permutations(sorted(a))]
i = p.index(a)
for a in p[max(0, i - 1):i + 2]:
	print(*a)


import itertools
n = input()
a = tuple(map(int, input().split()))
p = sorted(list(itertools.permutations(a)))
i = p.index(a)
if i > 0:
	print(*p[i - 1])
print(*p[i])
if i < len(p) - 1:
	print(*p[i + 1])


def resolve():
	import itertools
	n = int(input())
	target = tuple((int(i) for i in input().split()))
	before = None
	found = False
	for a in sorted(itertools.permutations(target)):
		if found:
			print(*a)
			return
		elif a == target:
			if before is not None:
				print(*before)
			print(*target)
			found = True
		else:
			before = a
resolve()


import itertools
n = int(input())
A = list(map(int, input().split()))
p = list(itertools.permutations(A))
A2 = sorted(p)
index = A2.index(tuple(A))
if index - 1 >= 0:
	print(*A2[index - 1])
print(*A2[index])
if index + 1 < len(A2):
	print(*A2[index + 1])


def next_permutation(a):
	if len(a) < 2:
		return False
	i = len(a) - 2
	while i >= 0 and a[i] >= a[i + 1]:
		i -= 1
	if i < 0:
		return False
	j = i + 1
	k = len(a) - 1
	while a[i] >= a[k]:
		k -= 1
	(a[i], a[k]) = (a[k], a[i])
	a[j:] = a[:j - 1:-1]
	return True

def prev_permutation(a):
	if len(a) < 2:
		return False
	i = len(a) - 2
	while i >= 0 and a[i] <= a[i + 1]:
		i -= 1
	if i < 0:
		return False
	j = i + 1
	k = len(a) - 1
	while a[i] <= a[k]:
		k -= 1
	(a[i], a[k]) = (a[k], a[i])
	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)


def solve():
	from sys import stdin
	f_i = stdin
	n = int(f_i.readline())
	A_s = f_i.readline().rstrip()
	if n == 1:
		print(A_s)
	else:
		A = tuple(map(int, A_s.split()))
		from itertools import permutations
		lex = tuple(permutations(range(1, n + 1), n))
		from bisect import bisect_left
		idx = bisect_left(lex, A)
		if idx == 0:
			print(A_s)
			print(' '.join(map(str, lex[idx + 1])))
		elif idx == len(lex) - 1:
			print(' '.join(map(str, lex[idx - 1])))
			print(A_s)
		else:
			print(' '.join(map(str, lex[idx - 1])))
			print(A_s)
			print(' '.join(map(str, lex[idx + 1])))
solve()


def next_permutation(a):
	if len(a) < 2:
		return False
	i = len(a) - 2
	while i >= 0 and a[i] >= a[i + 1]:
		i -= 1
	if i < 0:
		return False
	j = i + 1
	k = len(a) - 1
	while a[i] >= a[k]:
		k -= 1
	(a[i], a[k]) = (a[k], a[i])
	a[j:] = a[:j - 1:-1]
	return True

def prev_permutation(a):
	if len(a) < 2:
		return False
	i = len(a) - 2
	while i >= 0 and a[i] <= a[i + 1]:
		i -= 1
	if i < 0:
		return False
	j = i + 1
	k = len(a) - 1
	while a[i] <= a[k]:
		k -= 1
	(a[i], a[k]) = (a[k], a[i])
	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)


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)
main()


import itertools
n = int(input())
now = tuple(map(int, input().split()))
seq = [i + 1 for i in range(n)]
seq2 = list(itertools.permutations(seq))
ind = 0
for (j, k) in enumerate(seq2):
	if k == now:
		ind = j
if ind == 0:
	print(*seq2[ind])
	if len(seq2) != 1:
		print(*seq2[ind + 1])
elif ind + 1 == len(seq2):
	print(*seq2[ind - 1])
	print(*seq2[ind])
else:
	print(*seq2[ind - 1])
	print(*seq2[ind])
	print(*seq2[ind + 1])


import itertools
import copy
n = int(input())
l = list(map(int, input().split()))
l2 = copy.deepcopy(l)
l.sort()
ans = []
for i in itertools.permutations(l, n):
	ans.append(list(i))
for i in range(len(ans)):
	if ans[i] == l2:
		if i - 1 >= 0:
			print(' '.join(map(str, ans[i - 1])))
		print(' '.join(map(str, ans[i])))
		if i != len(ans) - 1:
			print(' '.join(map(str, ans[i + 1])))
		break


from itertools import permutations
N = int(input())
A = tuple(map(int, input().split()))
(*PS,) = permutations(range(1, N + 1), r=N)
i = PS.index(A)
if i > 0:
	print(*PS[i - 1])
print(*A)
if i < len(PS) - 1:
	print(*PS[i + 1])


from itertools import permutations
input()
L = [int(x) for x in input().split()]
k = tuple(L)
prev = None
L.sort()
f = 0
for s in permutations(L):
	if s == k:
		if prev:
			print(*prev)
		print(*s)
		f += 1
	elif f > 0:
		print(*s)
		break
	prev = s


import itertools
n = int(input())
a = tuple(map(int, input().split()))
if n == 1:
	print(a[0])
else:
	b = tuple(sorted(a))
	A = list(itertools.permutations(b))
	count = len(A) - 1
	if A.index(a) == count:
		print(' '.join(map(str, A[count - 1])))
		print(' '.join(map(str, a)))
	elif A.index(a) == 0:
		print(' '.join(map(str, b)))
		print(' '.join(map(str, A[1])))
	else:
		print(' '.join(map(str, A[A.index(a) - 1])))
		print(' '.join(map(str, a)))
		print(' '.join(map(str, A[A.index(a) + 1])))


from itertools import permutations
n = int(input())
A = tuple(map(int, input().split()))
res = [p for p in permutations(sorted(A), n)]
i = res.index(A)
for a in res[max(0, i - 1):i + 2]:
	print(*a)


import itertools

def print_elements(a):
	print(' '.join(list(map(str, a))))
n = int(input())
a = tuple(map(int, input().split(' ')))
permutations = list(itertools.permutations([i + 1 for i in range(n)]))
for (i, per) in enumerate(permutations):
	if per == a:
		if i != 0:
			print_elements(permutations[i - 1])
		print_elements(a)
		if i != len(permutations) - 1:
			print_elements(permutations[i + 1])


from itertools import permutations
n = int(input())
a = list(map(int, input().split()))
s = []
for i in permutations(sorted(a)):
	s.append(list(i))
for i in range(len(s)):
	if s[i] == a:
		if i > 0:
			print(*s[i - 1])
		print(*s[i])
		if i < len(s) - 1:
			print(*s[i + 1])
		break


from itertools import permutations
n = int(input())
arr = tuple(map(int, input().split()))
p = list(permutations(sorted(arr)))
idx = p.index(arr)
for i in range(max(0, idx - 1), min(len(p), idx + 2), 1):
	print(*p[i])