human
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...
 ... Write me a Python program to find the lexicographically minimal and lexicographically maximal permutations that could have been originally presented to Polycarp?
assistant
#Here is Python program to find the lexicographically minimal and lexicographically maximal permutations that could have been originally presented to Polycarp.

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:
                   ...