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:
#------------------Important Modules------------------#
from sys import stdin,stdout
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import *
from random import *
input=stdin.readline
prin=stdout.write
from random import sample
from collections import Counter,deque
from math import sqrt,ceil,log2,gcd
#dist=[0]*(n+1)
mod=10**9+7
"""
class DisjSet: 
    def __init__(self, n): 
        # Constructor to create and 
        # initialize sets of n items 
        self.rank = [1] * n 
        self.parent = [i for i in range(n)] 
  
  
    # Finds set of given item x 
    def find(self, x): 
          
        # Finds the representative of the set 
        # that x is an element of 
        if (self.parent[x] != x): 
              
            # if x is not the parent of itself 
            # Then x is not the representative of 
            # its set, 
            self.parent[x] = self.find(self.parent[x]) 
              
            # so we recursively call Find on its parent 
            # and move i's node directly under the 
            # representative of this set 
  
        return self.parent[x] 
  
  
    # Do union of two sets represented 
    # by x and y. 
    def union(self, x, y): 
          
        # Find current sets of x and y 
        xset = self.find(x) 
        yset = self.find(y) 
  
        # If they are already in same set 
        if xset == yset: 
            return
  
        # Put smaller ranked item under 
        # bigger ranked item if ranks are 
        # different 
        if self.rank[xset] < self.rank[yset]: 
            self.parent[xset] = yset 
  
        elif self.rank[xset] > self.rank[yset]: 
            self.parent[yset] = xset 
  
        # If ranks are same, then move y under 
        # x (doesn't matter which one goes where) 
        # and increment rank of x's tree 
        else: 
            self.parent[yset] = xset 
            self.rank[xset] = self.rank[xset] + 1
  
# Driver code 
"""


def f(arr,i,j,d,dist):
    if i==j:
        return 
    nn=max(arr[i:j])
    for tl in range(i,j):
        if arr[tl]==nn:
            dist[tl]=d
            #print(tl,dist[tl])
            f(arr,i,tl,d+1,dist)
            f(arr,tl+1,j,d+1,dist)
    #return dist
            
        
def ps(n):
    cp=0;lk=0;arr={}
    #print(n)
    cc=0;ans=1;
    while n%2==0:
        n=n//2
        #arr.append(n);arr.append(2**(lk+1))
        lk+=1
        cc=1;
    if lk%2==1:
        ans*=2
    
        
    for ps in range(3,ceil(sqrt(n))+1,2):
        lk=0
        cc=0
        while n%ps==0:
            n=n//ps
            cc=1
            #arr.append(n);arr.append(ps**(lk+1))
            lk+=1
        if lk%2==1:
            ans*=ps 
            
            
    if n!=1:
        #lk+=1
        #arr[n]=1
        ans*=n;
        #return arr
    
    #print(arr)
    
    return ans


#count=0
#dp=[[0 for i in range(m)] for j in range(n)]
#[int(x) for x in input().strip().split()]
def gcd(x, y): 
      
    while(y): 
        x, y = y, x % y 
      
    return x 
          
# Driver Code         
def factorials(n,r):
    #This calculates ncr mod 10**9+7
    slr=n;dpr=r
    qlr=1;qs=1
    mod=10**9+7
    
    for ip in range(n-r+1,n+1):
        qlr=(qlr*ip)%mod
    for ij in range(1,r+1):
        qs=(qs*ij)%mod
    #print(qlr,qs)
    ans=(qlr*modInverse(qs))%mod
    return ans

        
        
def modInverse(b):
    qr=10**9+7
    return pow(b, qr - 2,qr)

#===============================================================================================
### START ITERATE RECURSION ###
from types import GeneratorType
def iterative(f, stack=[]):
  def wrapped_func(*args, **kwargs):
    if stack: return f(*args, **kwargs)
    to = f(*args, **kwargs)
    while True:
      if type(to) is GeneratorType:
        stack.append(to)
        to = next(to)
        continue
      stack.pop()
      if not stack: break
      to = stack[-1].send(to)
    return to
  return wrapped_func
def power(arr):
  listrep = arr
  subsets = []
  for i in range(2**len(listrep)):
    subset = []
    for k in range(len(listrep)):            
      if i & 1<<k:
        subset.append(listrep[k])
    subsets.append(subset)        
  return subsets
def pda(n) :
    list = [] 
    for i in range(1, int(sqrt(n) + 1)) :
         if (n % i == 0) :
            if (n // i == i) :
                list.append(i)
            else :
                list.append(n//i);list.append(i)
                 
    # The list will be printed in reverse    
    return list
def dis(xa,ya,xb,yb):
    return sqrt((xa-xb)**2+(ya-yb)**2)
#### END ITERATE RECURSION ####
 
#===============================================================================================
#----------Input functions--------------------#
def ii():
    return int(input())
def ilist():
    return [int(x) for x in input().strip().split()]
def islist():
    return list(map(str,input().split().rstrip()))
def outfast(arr:list)->str:
    ss=''
    for ip in arr:
        ss+=str(ip)+' '
    ss+='\n'
    return prin(ss);
def kk(n):
    kp=0
    while n%2==0:
        n=n//2
        kp+=1
    if n==1:
        return [True,kp]
    else:
        return [False,0]
def google(test,ans):
    return "Case #"+str(test)+": "+str(ans);
###-------------------------CODE STARTS HERE--------------------------------###########
#########################################################################################
t=int(input())
#t=1

        
            
                
        
    
for jj in range(t):
    n=ii()
    arr=ilist()
    mins=[0]*n
    maxs=[0]*n
    mins[0]=maxs[0]=arr[0]
    nu=1;
    temp=[]
    mi={arr[0]};ma={arr[0]}
    for bp in range(1,arr[0]):
                temp.append(bp)
    prev=arr[0];
    for i in range(1,n):
        if arr[i]!=arr[i-1]:
            mins[i]=arr[i]
            mi.add(arr[i]);
            nt=arr[i];
            maxs[i]=arr[i];
            for bp in range(prev+1,arr[i]):
                temp.append(bp)
            

            
            prev=arr[i];
                
        else:
            while nu in mi:
                nu+=1
            mins[i]=nu
            mi.add(nu)
            #ma.add(nt)
            maxs[i]=temp.pop();
            
        #print(mi,ma)
    print(*mins);print(*maxs)
    #outfast(mins);outfast(maxs);