Problem: A permutation is a sequence of n integers from 1 to n, in which all numbers occur exactly once. For example, [1], [3, 5, 2, 1, 4], [1, 3, 2] are permutations, and [2, 3, 2], [4, 3, 1], [0] are not.

Polycarp was presented with a permutation p of numbers from 1 to n. However, when Polycarp came home, he noticed that in his pocket, the permutation p had turned into an array q according to the following rule: 

  * q_i = max(p_1, p_2, …, p_i). 



Now Polycarp wondered what lexicographically minimal and lexicographically maximal permutations could be presented to him.

An array a of length n is lexicographically smaller than an array b of length n if there is an index i (1 ≤ i ≤ n) such that the first i-1 elements of arrays a and b are the same, and the i-th element of the array a is less than the i-th element of the array b. For example, the array a=[1, 3, 2, 3] is lexicographically smaller than the array b=[1, 3, 4, 2].

For example, if n=7 and p=[3, 2, 4, 1, 7, 5, 6], then q=[3, 3, 4, 4, 7, 7, 7] and the following permutations could have been as p initially: 

  * [3, 1, 4, 2, 7, 5, 6] (lexicographically minimal permutation); 
  * [3, 1, 4, 2, 7, 6, 5]; 
  * [3, 2, 4, 1, 7, 5, 6]; 
  * [3, 2, 4, 1, 7, 6, 5] (lexicographically maximum permutation). 



For a given array q, find the lexicographically minimal and lexicographically maximal permutations that could have been originally presented to Polycarp.

Input

The first line contains one integer t (1 ≤ t ≤ 10^4). Then t test cases follow.

The first line of each test case contains one integer n (1 ≤ n ≤ 2 ⋅ 10^5).

The second line of each test case contains n integers q_1, q_2, …, q_n (1 ≤ q_i ≤ n).

It is guaranteed that the array q was obtained by applying the rule from the statement to some permutation p.

It is guaranteed that the sum of n over all test cases does not exceed 2 ⋅ 10^5.

Output

For each test case, output two lines: 

  * on the first line output n integers — lexicographically minimal permutation that could have been originally presented to Polycarp; 
  * on the second line print n integers — lexicographically maximal permutation that could have been originally presented to Polycarp; 

Example

Input


4
7
3 3 4 4 7 7 7
4
1 2 3 4
7
3 4 5 5 5 7 7
1
1


Output


3 1 4 2 7 5 6 
3 2 4 1 7 6 5 
1 2 3 4 
1 2 3 4 
3 4 5 1 2 7 6 
3 4 5 2 1 7 6 
1 
1 

Solution (in PYTHON3):

Solution:
class SegmentTree:
    def __init__(self, array, f = lambda x, y: x + y, inf = 0):
        self.f = f
        self.id = inf
        if isinstance(array, int):
            self.n = array
            self.tree = [self.id] * (self.n << 1)

        else:
            #self.height = (len(array) - 1).bit_length()
            #self.n = 1 << (self.height)
            self.n = len(array)
            self.tree = [self.id] * (self.n << 1)
            for i in range(len(array)):
                self.tree[self.n + i] = array[i]
            for i in range (self.n - 1, 0, -1):
                self.tree[i] = self.f (self.tree[i << 1], self.tree[i << 1 | 1])



    def get(self, i):
        return self.tree[i + self.n]


    def update(self, i, x):
        i += self.n
        self.tree[i] = x
        while i > 1:
            i >>= 1
            self.tree[i] = self.f (self.tree[i << 1], self.tree[i << 1 | 1])


    def query(self, l, r):
        l += self.n
        r += self.n
        lf, rf = self.id, self.id
        while l < r:
            if l & 1:
                lf = self.f (lf, self.tree[l])
                l += 1
            if r & 1:
                r -= 1
                rf = self.f (self.tree[r], rf)
            l >>= 1
            r >>= 1
        return self.f (lf, rf)


    def query_all(self):
        return self.tree[1]


    def display(self):
        for i in range(self.n, self.n << 1):
            print(self.tree[i], end=" ")
            while i % 2 == 0:
                i >>= 1
                print(self.tree[i], end=" ")
            print()


    def min_left(self, l, r, f, sss):
        nr = r
        lv, rv = [], []

        l += self.n
        r += self.n

        while l < r:
            if l & 1:
                lv.append(l)
                l += 1
            if r & 1:
                r -= 1
                rv.append(r)
            l >>= 1
            r >>= 1

        now = self.id
        for i in lv + rv[::-1]:
            if f(now, self.tree[i], sss):
                while True:
                    if f(now, self.tree[i], sss):
                        if i >= self.n:
                            return i - self.n + 1
                        i <<= 1
                    else:
                        now = self.f(now, self.tree[i])
                        i += 1
            else:
                now = self.f(now, self.tree[i])

        return nr + 1


    def max_right(self, l, r, f, sss):
        nl = l
        lv, rv = [], []

        l += self.n
        r += self.n

        while l < r:
            if l & 1:
                lv.append(l)
                l += 1
            if r & 1:
                r -= 1
                rv.append(r)
            l >>= 1
            r >>= 1

        now = self.id
        for i in rv + lv[::-1]:
            if f(self.tree[i], now, sss):
                while True:
                    if f(self.tree[i], now, sss):
                        if i >= self.n:
                            return i - self.n + 1
                        i <<= 1
                        i += 1
                    else:
                        now = self.f(self.tree[i], now)
                        i -= 1
            else:
                now = self.f(self.tree[i], now)

        return nl

import sys
input=sys.stdin.readline
t = int(input())
while t:
    t -= 1
    n = int(input())
    p = list(map(int, input().split()))
    ma = [p[0]]
    mi = [p[0]]
    a = [i for i in range(n + 1)]
    a[p[0]] = 1e9
    a[0] = 1e9
    S2 = SegmentTree(a, min, 1e9)
    a[p[0]] = -1
    a[0] = -1
    S1 = SegmentTree(a, max, -1)
    for i in range(n - 1):
        if p[i] == p[i + 1]:
            r = S1.query(0, p[i + 1])
            s = S2.query(0, p[i + 1])
            ma.append(r)
            mi.append(s)
            S1.update(r, -1)
            S2.update(s, 1e9)
        else:
            ma.append(p[i + 1])
            mi.append(p[i + 1])
            S1.update(p[i + 1], -1)
            S2.update(p[i + 1], 1e9)
    print(*mi)
    print(*ma)