Sorting

Description

For a given permutation of $,$ noting it as $,$ you need to insert the number in into a set

one by one, i$.$e$..$

After the insertion of each number, you need to find the largest number in that is smaller than

the inserted number and the smallest number in that is larger than the inserted number.

Initially, two integers has already been inserted into so that the results always exist.

Input

The input contains multiple test cases. The first line of the input contains an integer $,$ indicating

the number of test cases.

For each test case, the first line contains a positive integer $.$ The second line contains

integers, separated by spaces, the $-$th integer of which denotes $.$

Output

For each test case, print lines, each line contains two integers separated by a space, the $-$th

line of which denotes the result required after the insertion of the $-$th number.

The first integer of a result represents the largest number in that is smaller than the inserted

number and the second one represents the smallest number in that is larger than the inserted

numbser.

Sample Input$/$Output

Input

$2$

$5$

$15243$

$2$

$12$

Output

$06$

$16$

$15$

$25$

$24$

$03$

$13$

$1...$n P P

S P$1,$ P$2,...,$ Pn$1,$ Pn

S

S

$0,$ n $+1$ S

T

n n

i Pi

n i

i

S

S

Constraint

$.$

It is guaranteed that is a permutation of $.$

Hint

To find all the results quickly enough, you may think about reverting the whole process.

$1<=$ n $<=10$

$5$

P $1...$n