Prefix Permutation solution codechef- You are given an array AA of length KK. Find any permutation PP of length NN such that only the prefixes of length AiAi (1≤i≤K1≤i≤K) form a permutation.

Prefix Permutation solution codechef

You are given an array AA of length KK. Find any permutation PP of length NN such that only the prefixes of length AiAi (1iK1≤i≤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 NN is an array where every element from 11 to NN occurs exactly once.

Input Format

  • The first line of the input contains a single integer TT – the number of test cases.
  • The first line of each test case contains two integers NN and KK – the length of the permutation to be constructed and the size of the array AA respectively.
  • The second line of each test case contains KK space-separated integers A1,A2,,AKA1,A2,…,AK denoting the array AA.

Output Format

For each test case, print a single line containing NN space-separated integers P1,,PNP1,…,PN (1PiN)(1≤Pi≤N). If there are multiple solutions, you may print any.

Constraints

  • 1T1051≤T≤105
  • 1KN1051≤K≤N≤105
  • 1A1<A2<<AK=N1≤A1<A2<⋯<AK=N
  • the sum of NN over all test cases does not exceed 51055⋅105

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.

    For Solution

    Click Here!

Leave a Comment

Your email address will not be published.