Prefix Permutation

 You are given an array 

A$A$ of length K$K$. Find any permutation P$P$ of length N$N$ such that only the prefixes of length Ai$A_i$ (1≤i≤K$1\le i\le K$) form a permutation.

Under the given constraints, it is guaranteed that there exists at least one permutation which satisfies the given condition.

If there are multiple solutions, you may print any.

Note: A permutation of length N$N$ is an array where every element from 1$1$ to N$N$ occurs exactly once.

Input Format

• The first line of the input contains a single integer T$T$ - the number of test cases.
• The first line of each test case contains two integers N$N$ and K$K$ - the length of the permutation to be constructed and the size of the array A$A$ respectively.
• The second line of each test case contains K$K$ space-separated integers A1,A2,…,AK$A_1,A_2,\dots ,A_K$ denoting the array A$A$.

Output Format

For each test case, print a single line containing N$N$ space-separated integers P1,…,PN$P_1,\dots ,P_N$ (1≤Pi≤N)$(1\le P_i\le N)$. If there are multiple solutions, you may print any.

Constraints

• 1≤T≤105$1\le T\le {10}^5$
• 1≤K≤N≤105$1\le K\le N\le {10}^5$
• 1≤A1<A2<⋯<AK=N$1\le A_1<A_2<\cdots <A_K=N$
• the sum of N$N$ over all test cases does not exceed 5⋅105$5\cdot {10}^5$

Sample Input 1 

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

Sample Output 1 

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

Explanation

Test case-1: [2,3,1,6,4,5,7,8]$[2,3,1,6,4,5,7,8]$ is valid permutation because

• Prefix of length 3=[2,3,1]$3=[2,3,1]$ is a permutation.
• Prefix of length 6=[2,3,1,6,4,5]$6=[2,3,1,6,4,5]$ is a permutation.
• Prefix of length 7=[2,3,1,6,4,5,7]$7=[2,3,1,6,4,5,7]$ is a permutation.
• Prefix of length 8=[2,3,1,6,4,5,7,8]$8=[2,3,1,6,4,5,7,8]$ is a permutation.
• None of the other prefixes form a permutation.

• Tweet
• Share
• Share
• Share
• Share

Related Post