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:
def mingrid():
    for _ in range(int(input())):
        n = int(input())
        segcost = input().split()
        minodd = int(segcost[0])
        mineven = int(segcost[1])
        sumodd = minodd
        sumeven = mineven
        codd = 1
        ceven = 1
        res = sumodd + minodd * (n - codd) + sumeven + mineven * (n - ceven)
        for i in range(2, n):
            now = int(segcost[i])
            if (i + 1) % 2:  # odd
                minodd = min(minodd, now)
                sumodd += now
                codd += 1
            else:
                mineven = min(mineven, now)
                sumeven += now
                ceven += 1
            res = min(res, sumodd + minodd * (n - codd) + sumeven + mineven * (n - ceven))
        print(res)


# mingrid()


def numofpairs():
    n = (10 * 2) ** 7 + 1
    l = [False] * n
    primes = []
    for i in range(2, n):
        if not l[i]:
            for i1 in range(i + i, n, i):
                l[i1] = True
            primes.append(i)
            l[i] = True
    tol = [0, 0]
    for i in range(2, n):
        pos = 0
        t = 0
        while i:
            val = primes[pos]
            if not i:
                tol.append(t)
                break
            elif i < val:
                tol.append(t + 1)
                break
            elif not i % val:
                i //= val
            else:
                pos += 1
                t += 1
    for _ in range(int(input())):
        c, d, x = map(int, input().split())
        lim = int(math.sqrt(x)) + 1
        ans = 0
        for i in range(1, lim):
            thing = i + d
            if thing % c:
                continue
            ans += (2 ** tol[thing // c])
        print(ans)


# numofpairs()

def restoremod():
    for _ in range(int(input())):
        length = int(input()) - 1
        l = input().split()
        # print("s")
        t = False
        ife = False
        for i in range(length):
            if int(l[i]) == int(l[i + 1]):
                if i > 0:
                    print(-1)
                    t = True
                    break
                else:
                    ife = True
            elif ife:
                print(-1)
                t = True
                break
        if not t:
            posc = 0
            negc = 0
            res = int(l[1]) - int(l[0])
            if res > 0:
                posc = res
            else:
                negc = res
            if not negc:
                for i in range(1, length):
                    now = int(l[i]) - int(l[i + 1])
                    if now > 0:
                        negc = now
                        break
            if not posc:
                for i in range(1, length):
                    change = int(l[i + 1]) - int(l[i])
                    if change > 0:
                        posc = change
                        break
            if posc and negc:
                mod = posc + negc
            else:
                mod = 0
            c = posc if posc else -negc
            larnum = 0
            for i in range(length):
                nowi = int(l[i])
                larnum = max(larnum, nowi)
                if larnum > mod and mod:
                    print(-1)
                    t = True
                    break
                res = int(l[i + 1]) - nowi
                if res < 0:
                    if res != -(mod - c):
                        print(-1)
                        t = True
                        break
                if res > 0:
                    if res != c:
                        t = True
                        print(-1)
                        break
            if not t:
                if mod:
                    print(mod, c, sep=' ')
                else:
                    print(mod)


# restoremod()

def restoremod1():
    for _ in range(int(input())):
        num = int(input())
        ...


def cells():
    for _ in range(int(input())):
        row, col, num = map(int, input().split())
        nr = ((num - 1) % row)
        nc = ((num - 1) // row) + 1
        print(nr * col + nc)


# cells()

def replacement():
    for _ in range(int(input())):
        l, k = map(int, input().split())
        s = input()
        left, righ = s.find('*'), s.rfind('*')
        if righ - left <= k:
            print(2 if righ != left else 1)
        else:
            pos = left
            c = 2
            while righ - pos > k:
                pos = pos + k
                while pos < l and s[pos] != '*':
                    pos -= 1
                c += 1
            print(c)


# replacement()

import math

import sys

input = sys.stdin.readline


def string():
    for _ in range(int(input())):
        s = input().rstrip()
        s1 = input().rstrip()
        # if s == s1:
        #     print(0)
        #     continue
        maxl = 0
        p1 = [0, 0]
        p = [0, 0]
        for i in range(len(s)):
            for i1 in range(i + 1, len(s) + 1):
                pos = s1.find(s[i:i1])
                if pos == -1:
                    break
                elif (i1 - i) <= maxl:
                    continue
                elif (i1 - i) > maxl:
                    maxl = i1 - i
                    p1 = [pos, pos + maxl]
                    p = [i, i + maxl]
        print(((p[0] + len(s) - p[1]) + (p1[0] + len(s1) - p1[1])) if maxl else len(s) + len(s1))


# string()

import collections


def trans(l):
    pos = 0
    while pos < len(l) - 1:
        avg = l[pos] // (len(l) - pos - 1)
        rem = l[pos] % (len(l) - pos - 1)
        l[pos] = 0
        for i in range(pos + 1, len(l)):
            l[i] -= avg
            if l[i] < 0:
                rem += -l[i]
                l[i] = 0
        while pos + 1 < len(l) and l[pos + 1] <= rem:
            rem -= l.pop(pos + 1)
        if pos + 1 < len(l):
            l[pos + 1] -= rem
        else:
            l[0] = rem
        pos += 1
    return sum(l)


# trans()
def trans1(l):
    pos = 0
    lenl = len(l)
    pos1 = pos + 1
    while pos1 < lenl and pos < lenl:
        while pos1 < lenl and l[pos] - l[pos1] >= 0:
            l[pos] -= l[pos1]
            l[pos1] = 0
            pos1 += 1
        if pos1 < lenl:
            l[pos1] -= l[pos]
            l[pos] = 0
            pos = pos1
            pos1 += 1
    return sum(l)


# print(trans1([9,8,2,1,1,1]))


def main():
    for _ in range(int(input())):
        num = input()
        l = sorted(list(collections.Counter(input().split()).values()), reverse=True)
        ans = trans(l[:])
        if ans:
            print(min(ans, trans1(l)))
        else:
            print(0)


# main()


def transrep():
    for _ in range(int(input())):
        num = int(input())
        l = list(collections.Counter(input().split()).values())
        ml = max(l)
        if ml > num - ml:
            print(ml - num + ml)
        else:
            print(num % 2)


# transrep()


def resmod():
    def solve():
        posc = -1
        negc = 1
        num = int(input())
        l = input().split()
        ifz = False
        maxi = int(l[0])
        for i in range(num - 1):
            maxi = max(maxi, int(l[i + 1]))
            c = int(l[i + 1]) - int(l[i])
            if c == 0:
                if not i:
                    ifz = True
                    continue
                elif not ifz:
                    return -1
            elif ifz:
                return -1
            elif c < 0:
                if negc == 1:
                    negc = c
                else:
                    if negc != c:
                        return -1
            elif c > 0:
                if posc == -1:
                    posc = c
                else:
                    if posc != c:
                        return -1
        if posc == -1 or negc == 1:
            return 0
        mod = posc + -negc
        if mod <= maxi:
            return -1
        return '{0} {1}'.format(mod, posc)

    for _ in range(int(input())):
        print(solve())


# resmod()


def basicdep():
    def findmax(l):
        ans = 0
        res = 0
        for i, v in enumerate(l):
            if ans < v:
                res = i
                ans = v
        return [res + 1, ans]  # pos,value

    def roundup(num):
        s = num / 2
        if s != int(s):
            return int(s) + 1
        return int(s)

    for _ in range(int(input())):
        days = []
        f, d = map(int, input().split())
        friends = [0] * f
        for i in range(d):
            nowfs = input().split()
            nowff = int(nowfs[1])
            friends[nowff - 1] += 1
            if int(nowfs[0]) > 1:
                days.append([nowff, int(nowfs[2])])
            else:
                days.append([nowff, []])
        maxl = findmax(friends)
        goal = roundup(d)
        if maxl[1] < goal:
            print('YES')
            print(*[i[0] for i in days], sep=' ')
        else:
            pos = 0
            while pos < d and maxl[1] > goal:
                if days[pos][0] == maxl[0] and days[pos][1]:
                    days[pos][0] = days[pos][1]
                    maxl[1] -= 1
                pos += 1
            if maxl[1] > goal:
                print('NO')
            else:
                print('YES')
                print(*[i[0] for i in days], sep=' ')


# basicdep()


def playlist():
    def nextsong(pos):
        while pos + 1 in ans and len(ans) != num:
            pos += 1
            if pos == num:
                pos = 0
        return pos

    def gcf(n, n1):
        if not n:
            return n1
        return gcf(n1, n % n1) if n1 else n

    for _ in range(int(input())):
        num = int(input())
        l = input().split()
        deletel = collections.deque()
        for i in range(num - 1):
            a, b = int(l[i]), int(l[i + 1])
            if gcf(a, b) == 1:
                deletel.append((i, i + 1))
        if gcf(int(l[-1]), int(l[0])) == 1:
            deletel.append((num - 1, 0))
        ans = dict()
        while deletel and len(ans) != num:
            a, b = deletel.popleft()
            if a + 1 in ans or b + 1 in ans:
                continue
            ans[b + 1] = True
            if deletel:
                if deletel[0][0] == b:
                    deletel.popleft()
            if b == num - 1:
                n = nextsong(0)
                if gcf(int(l[a]), int(l[n])) == 1:
                    deletel.append((a, n))
            else:
                n = nextsong(b + 1)
                if gcf(int(l[a]), int(l[n])) == 1:
                    deletel.append((a, n))
        print(len(ans), *ans.keys(), sep=' ')


# playlist()

def shoesandst():
    students, laces, = map(int, input().split())
    d = collections.defaultdict(list)
    rems = set()
    for _ in range(laces):
        a, b = map(int, input().split())
        d[a].append(b)
        d[b].append(a)
        lisa = d[a]
        lisb = d[b]
        la = len(lisa)
        lb = len(lisb)
        if la == 2:
            rems.discard((a, lisa[0]))
        elif la == 1:
            rems.add((a, b))
        if lb == 2:
            rems.discard((b, lisb[0]))
        elif lb == 1:
            rems.add((b, a))
    c = 0
    nextans = set()
    while rems or nextans:
        nextans.clear()
        while rems:
            a, b = rems.pop()
            nextans.discard((a, b))
            nextans.discard((b, a))
            d[a].pop()  # may not needed
            d[b].remove(a)
            lb = len(d[b])
            if not lb:
                rems.discard((b, a))
            if lb == 1:
                nextans.add((b, d[b][0]))
        rems = nextans.copy()
        c += 1
    return c


# print(shoesandst())
import heapq


def restoreperm():
    for _ in range(int(input())):
        length = int(input())
        maxselect = []
        minselect = []
        ansma = []
        ansmi = []
        last = 0
        for i in input().split():
            i = int(i)
            if i == last:
                ansma.append(-heapq.heappop(maxselect))
                ansmi.append(heapq.heappop(minselect))
            else:
                ansma.append(i)
                ansmi.append(i)
                for num in range(last+1,i):
                    heapq.heappush(maxselect, -num)
                    heapq.heappush(minselect, num)
                last = i
        print(*ansmi,sep=' ')
        print(*ansma,sep=' ')
restoreperm()