You are given an array A of length K. Find any permutation P of length N such that only the prefixes of length A_{i} (1 ≤ 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 N is an array where every element from 1 to N occurs exactly once.

------ Input Format ------ 

- The first line of the input contains a single integer T - the number of test cases. 
- The first line of each test case contains two integers N and K - the length of the permutation to be constructed and the size of the array A respectively.
- The second line of each test case contains K space-separated integers A_{1}, A_{2}, \dots, A_{K} denoting the array A.

------ Output Format ------ 

For each test case, print a single line containing N space-separated integers P_{1}, \dots, P_{N} (1 ≤ P_{i} ≤ N). If there are multiple solutions, you may print any.

------ Constraints ------ 

$1 ≤T ≤10^{5}$
$1 ≤K ≤N ≤10^{5}$
$1 ≤A_{1} < A_{2} < \dots < A_{K} = N$
- the sum of $N$ over all test cases does not exceed $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 1 ------ 
Test case-1: $[2, 3, 1, 6, 4, 5, 7, 8]$ is valid permutation because 
- Prefix of length $3 = [2, 3, 1]$ is a permutation. 
- Prefix of length $6 = [2, 3, 1, 6, 4, 5]$ is a permutation.
- Prefix of length $7 = [2, 3, 1, 6, 4, 5, 7]$ is a permutation.
- Prefix of length $8 = [2, 3, 1, 6, 4, 5, 7, 8]$ is a permutation.
- None of the other prefixes form a permutation.

Difficulty: MEDIUM
Tags: Constructive algorithms

Starter code:

Solutions:
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	j = 1
	pre = 0
	for i in a:
		for k in range(i, pre, -1):
			print(k, end=' ')
		pre = i
	print()


from math import sqrt, ceil, floor, gcd, log2
import sys
from sys import stdin, stdout
from collections import Counter, defaultdict, OrderedDict, deque
from itertools import combinations, groupby
from time import time
from heapq import heappop, heappush, heapify
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = [0] + list(range(1, n + 1))
	c = 1
	for i in a:
		m = [b[i]] + b[c:i]
		b[c:i + 1] = m
		c = i + 1
	print(*b[1:])


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = [0] + list(range(1, n + 1))
	c = 1
	for i in a:
		m = [b[i]] + b[c:i]
		b[c:i + 1] = m
		c = i + 1
	print(*b[1:])


tests = int(input())
for i in range(tests):
	(requried, prefixes) = map(int, input().split())
	prefix = list(map(int, input().split()))
	arr = [i for i in range(1, requried + 1)]
	exchange = 0
	for j in range(prefixes):
		(arr[prefix[j] - 1], arr[exchange]) = (arr[exchange], arr[prefix[j] - 1])
		exchange = prefix[j]
	print(*arr)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	Ai = list(map(int, input().split()))
	pr = [i for i in range(1, n + 1)]
	cnt = 0
	i = 0
	intial = 0
	Ai.sort()
	while cnt < n:
		current = 0
		if cnt == 0:
			current = Ai[i] - intial
			print(Ai[i], *pr[cnt:cnt + current - 1], end=' ')
		else:
			current = Ai[i] - Ai[i - 1]
			print(Ai[i], *pr[cnt:cnt + current - 1], end=' ')
		cnt += current
		i += 1
	print()


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l = sorted(map(int, input().split()))
	l.insert(0, 0)
	for j in range(k):
		for z in range(l[j + 1], l[j], -1):
			print(z, end=' ')
	print()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	indices = sorted(map(int, input().split()))
	indices.insert(0, 0)
	for i in range(k):
		for i in range(indices[i + 1], indices[i], -1):
			print(i, end=' ')
	print()


for _ in range(int(input())):
	(size, leng) = map(int, input().split())
	a = list(map(int, input().split()))
	p = []
	j = 0
	for i in range(size):
		p.append(i + 1)
	for i in range(leng):
		p[j:a[i]] = reversed(p[j:a[i]])
		j = a[i]
	print(*p)


mod = 1000000007
from sys import stdin, stdout
input = stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	li = list(map(int, input().split()))
	li.sort()
	ans = []
	for i in range(k):
		if i == 0:
			for j in range(li[i], 0, -1):
				ans.append(j)
		else:
			for j in range(li[i], li[i - 1], -1):
				ans.append(j)
	print(*ans)


for j in range(int(input())):
	(n, k) = map(int, input().split())
	arr = [int(x) for x in input().split()]
	res = []
	for i in range(n):
		res.append(i + 1)
	pt = 0
	for i in range(k):
		(res[pt], res[arr[i] - 1]) = (res[arr[i] - 1], res[pt])
		pt = arr[i]
	for i in res:
		print(i, end=' ')
	print()


t = int(input())
for j in range(t):
	(n, k) = map(int, input().split())
	arr = [int(i) for i in input().split()]
	ans = []
	for i in range(0, k):
		if i == 0:
			old = 1
		else:
			old = arr[i - 1] + 1
		new = arr[i]
		while new > old - 1:
			ans.append(new)
			new -= 1
	for h in ans:
		print(h, end=' ')
	print()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l1 = list(map(int, input().split()))
	m = 1
	q = 2
	p = l1[0]
	c = 0
	for i in range(n):
		if p == i + 1:
			print(m, end=' ')
			c = c + 1
			if c < k:
				p = l1[c]
			m = q
			q = m + 1
		else:
			print(q, end=' ')
			q = q + 1
	print()


tl = int(input())
while tl:
	tl = tl - 1
	(n, l) = map(int, input().split())
	arr = list(map(int, input().split()))
	k = 1
	arr.insert(0, 0)
	for i in range(n):
		print(arr[k] - i + arr[k - 1], end=' ')
		if arr[k] == i + 1:
			k = k + 1
	print()


try:
	for _ in range(int(input())):
		(n, k) = map(int, input().split())
		l = list(map(int, input().split()))
		prev = 1
		for i in range(k):
			n = l[i]
			for j in range(n, prev - 1, -1):
				print(j, end=' ')
			prev = n + 1
		print()
except Exception:
	pass


for _ in range(int(input())):
	(n, k) = (int(t) for t in input().split())
	a = [int(x) for x in input().split()]
	curr = 0
	for (i, val) in enumerate(a):
		while val > curr:
			print(val, end=' ')
			val -= 1
		curr = a[i]
	for j in range(a[-1] + 1, n + 1):
		print(j, end=' ')
	print()


T = int(input())
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	A = [int(x) for x in input().split()]
	P = []
	for a in A:
		L = [i + 1 for i in range(len(P), a)]
		L.append(L.pop(0))
		P.extend(L)
	print(*P)


t = int(input())
for i in range(t):
	l = input().split(' ')
	l1 = [int(v) for v in l]
	l2 = [[x + 1, 0] for x in range(l1[0])]
	l2[-1][1] = 1
	l1 = input().split(' ')
	for p in range(len(l1)):
		l1[p] = int(l1[p])
		l2[l1[p] - 1][1] = 1
	l2 = l2[::-1]
	for k in range(len(l2)):
		if l2[k][1] == 1:
			flag = k
		else:
			(l2[k][0], l2[flag][0]) = (l2[flag][0], l2[k][0])
			flag = k
	l2 = l2[::-1]
	for item in l2:
		print(item[0], end=' ')
	print('')


t = int(input())
while t > 0:
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	arr = list(map(int, input().split()))
	i = 0
	init = i
	for j in range(k):
		end = arr[j]
		y = arr[j]
		for l in range(init, end):
			print(y, end=' ')
			y -= 1
		init = end
	print()
	t -= 1


t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	arr = [0] + list(map(int, input().split()))
	ans = []
	for i in range(len(arr) - 1):
		lst = list(range(arr[i] + 1, arr[i + 1] + 1))
		ans += lst[::-1]
	print(*ans)
	t -= 1


t = int(input())
for i in range(t):
	(x, n) = map(int, input().split())
	l = [int(n) for n in input().split()]
	l.sort()
	k = []
	if n == 1 and l[0] == x:
		for i in range(x, 0, -1):
			print(i, end=' ')
		print()
		continue
	m = 0
	for i in range(0, n, 1):
		for p in range(l[i], m, -1):
			print(p, end=' ')
		m = l[i]
	print()


for _ in range(0, int(input())):
	(n, k) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	a.sort()
	p = []
	curr = 1
	temp = curr
	for i in range(len(a)):
		temp = curr
		if i != 0:
			for j in range(a[i] - a[i - 1] - 1):
				p.append(curr + 1)
				curr += 1
		else:
			for j in range(a[i] - 1):
				p.append(curr + 1)
				curr += 1
		p.append(temp)
		curr += 1
	print(*p)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	ans = [0 for i in range(max(l))]
	prev = 0
	c = 0
	for i in range(len(l)):
		for k in range(l[i], prev, -1):
			ans[c] = k
			c += 1
		prev = l[i]
	print(*ans)


def reverse_subarray(l, r):
	i = l - 1
	j = r - 1
	while i < j:
		(lst[i], lst[j]) = (lst[j], lst[i])
		i += 1
		j -= 1
for t in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	lst_k = [int(x) for x in input().split()]
	start = 1
	lst = [int(x) for x in range(1, n + 1)]
	for i in range(k):
		l = start
		r = lst_k[i]
		reverse_subarray(l, r)
		start = r + 1
	for x in lst:
		print(x, end=' ')
	print()


import numpy as np
np.array([1, 2, 3, 4, 5])
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	lst = [int(x) for x in input().split()]
	temp1 = 1
	for i in range(k):
		print(lst[i], end=' ')
		for j in range(temp1, lst[i]):
			print(j, end=' ')
		temp1 = lst[i] + 1
	print()


def func(s, e):
	while s >= e:
		print(s, end=' ')
		s -= 1
for i in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	c = 1
	for j in range(k):
		func(arr[j], c)
		c = arr[j] + 1
	print()


import math, os, io, heapq
from functools import reduce
from sys import stdin, stdout
from collections import Counter, deque, defaultdict
from itertools import product
import bisect

def getList(method=int):
	return list(map(method, input().split()))

def getInt():
	return int(input())

def solve():
	(n, k) = getList()
	arr = getList()
	(end, ans) = (0, [])
	for i in range(k):
		for v in range(arr[i], end, -1):
			ans.append(v)
		end = arr[i]
	print(*ans)
for _ in range(getInt()):
	solve()


t = int(input())
for i in range(t):
	(N, K) = map(int, input().split())
	a = list(map(int, input().split()))
	b = 0
	ans = []
	for j in range(len(a)):
		for k in range(a[j], b, -1):
			ans.append(k)
		b = a[j]
	print(*ans)


t = int(input())
while t:
	(n, k) = map(int, input().split())
	a = [int(i) for i in input().split()]
	c = []
	x = set()
	for i in range(1, n + 1):
		x.add(i)
		c.append(i)
	for i in range(k):
		y = a[i]
		if y in x:
			x.remove(y)
	m = list(x)
	b = []
	for i in range(len(m)):
		b.append(m[i] - 1)
	if len(b) == 0:
		for i in range(len(c)):
			print(c[i], end=' ')
	else:
		for i in range(len(b)):
			m = b[i]
			(c[m], c[m + 1]) = (c[m + 1], c[m])
		for i in range(len(c)):
			print(c[i], end=' ')
	print()
	t = t - 1


t = int(input())
while t != 0:
	(n, k) = input().split()
	N = int(n)
	K = int(k)
	A = input().split()
	for i in range(K):
		A[i] = int(A[i])
	c = 0
	while c != N:
		for i in A:
			for j in range(i, c, -1):
				print(j, end=' ')
				c = c + 1
	print()
	c = 0
	t = t - 1


from itertools import chain
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	l.insert(0, 0)
	v = []
	for i in range(k):
		v.append(list(range(l[i + 1], l[i], -1)))
	print(*list(chain(*v)))


t = int(input())
for _ in range(t):
	(N, K) = list(map(int, input().split(' ')))
	A = list(map(int, [0] + input().split(' ')))
	l = []
	for i in range(1, K + 1):
		l.extend(list(range(A[i], A[i - 1], -1)))
	print(*l, sep=' ')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l = [0] + l
	ans = []
	for i in range(k):
		for j in reversed(range(l[i] + 1, l[i + 1] + 1)):
			ans.append(j)
	print(*ans)


for _ in range(int(input())):
	(N, K) = [int(x) for x in input().split()]
	A = sorted([int(x) for x in input().split()])
	P = []
	nxt = 1
	for a in A:
		old_nxt = nxt
		while nxt != a:
			nxt += 1
			P.append(nxt)
		P.append(old_nxt)
		nxt += 1
	print(*P)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = [int(x) for x in input().split()]
	ans = []
	last = 1
	for i in range(k):
		part = [x for x in range(last, a[i] + 1)]
		ans += part[::-1]
		last = a[i] + 1
	print(*ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	list1 = []
	list1 = list((x for x in map(int, input().split())))
	list1.insert(0, 0)
	list2 = []
	for i in range(1, k + 1):
		for j in range(list1[i], list1[i - 1], -1):
			list2.append(j)
	print(*list2)


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
from math import ceil, floor, gcd

def inp():
	return int(input())

def lis():
	return list(map(int, input().split()))

def ma():
	return map(int, input().split())

def st():
	return input().rstrip('\n')

def isPrime(n):
	if n == 1:
		return 0
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return 0
	return 1

def euc(x1, y1, x2, y2):
	return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5

def counter(a):
	d = dict()
	for i in a:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	return d

def alpha(a):
	d = [0 for i in range(26)]
	for i in a:
		d[ord(i) - 97] += 1
	return d
t = inp()
for _ in range(t):
	(n, k) = ma()
	a = lis()
	ans = []
	j = 0
	now = []
	for i in range(1, n + 1):
		if j == k:
			now.append(i)
			continue
		if i == a[j]:
			j += 1
			now.append(i)
			now = now[::-1]
			for r in now:
				ans.append(r)
			now = []
		else:
			now.append(i)
	if len(now):
		for k in now:
			ans.append(k)
	print(*ans)


t = int(input())
while t != 0:
	t -= 1
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	q = 0
	new = []
	for i in a:
		new1 = i
		new2 = i
		for j in range(q, new2):
			new.append(new1)
			new1 -= 1
		q = new2
	print(*new)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	m = 0
	init = m
	for j in range(k):
		end = a[j]
		y = a[j]
		for l in range(init, end):
			print(y, end=' ')
			y -= 1
		init = end
	print()
	t -= 1


import random
T = int(input())
for t in range(T):
	(N, K) = map(int, input().split())
	A = []
	start = 1
	K_list = list(map(int, input().split()))
	K_list.sort()
	for k_list in K_list:
		temp_list = list(range(start, k_list + 1, 1))
		last_item = temp_list.pop(0)
		start = k_list + 1
		random.shuffle(temp_list)
		temp_list.append(last_item)
		A.extend(temp_list)
	print(*A, sep=' ')


import itertools
import collections, math
from collections import defaultdict
from collections import Counter
import sys
for t in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	a.sort()
	ans = []
	start = 1
	for x in a:
		for i in range(x, start - 1, -1):
			ans.append(i)
		start = x + 1
	if len(ans) != n:
		for i in range(n, start - 1, -1):
			ans.append(i)
	print(*ans)


for T in range(int(input())):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	L = list(range(1, N + 1))
	B = 0
	for i in A:
		L.insert(B, L.pop(i - 1))
		B = i
	print(*L)


from collections import Counter
from math import ceil, floor, log, gcd
import bisect as bs
import sys
input = sys.stdin.readline
inp_lis = lambda : list(map(int, input().split()))
inp_multi = lambda : map(int, input().split())
inp_int = lambda : int(input().strip())
for _ in range(int(input().strip())):
	(n, k) = inp_multi()
	a = inp_lis()
	l = []
	i = 0
	for each in a:
		temp = each
		while temp > i:
			l.append(temp)
			temp -= 1
		i = each
	print(*l)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	ans = []
	t = 1
	f = 0
	for i in range(2, n + 2):
		if i - 1 == arr[f]:
			print(t, end=' ')
			t = arr[f] + 1
			f += 1
			continue
		print(i, end=' ')
	print()


T = int(input())
for test in range(T):
	(N, K) = map(int, input().split())
	A = [int(k) for k in input().split()]
	ind = 0
	ans = []
	while ind < K:
		t = A[ind]
		current = len(ans)
		for i in range(t, current, -1):
			ans.append(i)
		ind += 1
	for i in ans:
		print(i, end=' ')
	print()


for i in range(int(input())):
	l1 = [int(x) for x in input().split()]
	l2 = [int(x) for x in input().split()]
	l = []
	for j in range(1, l1[0] + 1):
		l.append(j)
	l[0:l2[0]] = l[l2[0] - 1::-1]
	for m in range(l1[1] - 1):
		l[l2[m]:l2[m + 1]] = l[l2[m + 1] - 1:l2[m] - 1:-1]
	for k in l:
		print(k, end=' ')
	print()


t = int(input())
test = []
for i in range(t):
	(n, k) = input().split()
	v = [int(j) for j in input().split()]
	test.append([n, k, v])
for i in test:
	l = []
	c = 0
	for j in i[2]:
		t = j
		while t > c:
			l.append(t)
			t -= 1
		c = j
	for j in l:
		print(j, end=' ')
	print()


try:
	for i in range(int(input())):
		(a, b) = map(int, input().split())
		c = list(map(int, input().split()))
		l = []
		s = 0
		for j in c:
			for k in range(j, s, -1):
				l.append(k)
			s = j
		print(*l)
except:
	pass


T = int(input())
for _ in range(T):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.insert(0, 0)
	na = []
	for i in range(k + 1):
		for j in range(arr[i], arr[i - 1], -1):
			na.append(j)
	print(*na)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	per = []
	c = 1
	for i in l:
		temp = []
		for j in range(c, i + 1):
			temp.append(j)
		per += temp[1:] + [temp[0]]
		c = i + 1
	print(*per)


for i in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	ar = [int(x) for x in input().split()]
	a = []
	c = 0
	for i in ar:
		b = [j for j in range(i, c, -1)]
		a.extend(b)
		c = i
	print(*a)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	ans = list(range(1, n + 1))
	pre = 0
	for i in arr:
		(ans[pre], ans[i - 1]) = (ans[i - 1], ans[pre])
		pre = i
	print(' '.join(map(str, ans)))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = []
	l = map(int, input().split())
	ans = []
	ma = 0
	for i in l:
		print(i, end=' ')
		for j in range(ma + 1, i):
			print(j, end=' ')
		ma = i
	print()


t = int(input())
while t > 0:
	(n, k) = [int(i) for i in input().split()]
	l = [int(i) for i in input().split()]
	x = []
	z = 1
	for i in l:
		x.append(i)
		x.extend(list(range(i - 1, z - 1, -1)))
		z = i + 1
	print(*x, sep=' ')
	t -= 1


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	l = []
	c = 0
	for x in range(k):
		for i in range(a[x], c, -1):
			l.append(i)
		c = a[x]
	print(*l)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	m = 0
	for x in a:
		for i in range(x, m, -1):
			print(i, end=' ')
		m = x
	print()


for i in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	r = []
	c = 0
	for i in range(k):
		k1 = a[i]
		while k1 > c:
			r.append(k1)
			k1 -= 1
		c = a[i]
	print(*r)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	c = 0
	a = []
	for j in l:
		h = list(range(j, c, -1))
		c = j
		a.extend(h)
	print(*a)


for u in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	p = []
	x = 0
	for i in range(k):
		for j in range(l[i], x, -1):
			p.append(j)
		x = l[i]
	for i in range(n, x, -1):
		p.append(i)
	print(*p)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l = [0] + l
	for i in range(1, len(l)):
		for j in range(l[i], l[i - 1], -1):
			print(j, end=' ')
	print()


for i in range(int(input())):
	(n, k) = map(int, input().split())
	ls0 = list(map(int, input().split()))
	ls1 = []
	prev = 0
	for i in ls0:
		end = i
		for j in range(prev, end):
			ls1.append(end)
			end -= 1
		prev = i
	ls2 = map(str, ls1)
	print(' '.join(ls2))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	op = []
	init = 0
	for i in arr:
		val = i
		while val > init:
			op.append(val)
			val -= 1
		init = i
	print(*op)


t = int(input(' '))
while t > 0:
	(N, K) = map(int, input(' ').split(' '))
	A = list(map(int, input(' ').split(' ')))
	P = []
	A.sort()
	intial = 1
	for i in range(K):
		ls = list(range(intial, A[i] + 1))
		mid = len(ls) // 2
		ls1 = ls[mid:]
		ls2 = ls[:mid]
		P += ls1 + ls2
		intial = A[i] + 1
	t -= 1
	for i in range(N):
		print(P[i], end=' ')
	print(' ')