Read problem statements in [Hindi],[Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Chef had a sequence $S_{0}, S_{1}, \ldots, S_{N-1}$; each element of this sequence was an integer between $0$ and $N-1$ (inclusive). Unfortunately, he forgot some (possibly zero or all) elements of this sequence. You are given a sequence $A_{0}, A_{1}, \ldots, A_{N-1}$, where for each valid $i$, $A_{i} = -1$ denotes an element Chef forgot and if $A_{i} \neq -1$, then $A_{i} = S_{i}$.

Before Chef forgot any elements of $S$, he created a sequence $B_{0}, B_{1}, \ldots, B_{N-1}$, where for each valid $i$, $B_{i}$ is the number of occurrences of the value $i$ in $S$ (the number of valid indices $j$ such that $S_{j} = i$), and then, he created a third sequence $G_{0}, G_{1}, \ldots, G_{N}$, where for each valid $i$, $G_{i}$ is the number of occurrences of the value $i$ in $B$. (Note that the elements of $B$ are between $0$ and $N$ inclusive.) Unfortunately, Chef also forgot the sequence $B$, but he remembers $G$.

Help Chef restore the missing elements of the sequence $S$. Precisely, find the lexicographically smallest sequence $S$ which is consistent with all the given information or determine that there is no such sequence.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
The second line contains $N$ space-separated integers $A_{0}, A_{1}, \ldots, A_{N-1}$.
The third line contains $N+1$ space-separated integers $G_{0}, G_{1}, \ldots, G_{N}$.

------  Output ------
For each test case:
If there is no sequence $S$ consistent with all the given information, print a single line containing the string "impossible".
Otherwise, print a single line containing $N$ space-separated integers $S_{0}, S_{1}, \ldots, S_{N-1}$ - the lexicographically smallest valid sequence $S$.

------  Constraints ------
$1 ≤ T ≤ 1,000$
$2 ≤ N ≤ 10^{5}$
$-1 ≤ A_{i} ≤ N-1$ for each valid $i$
$0 ≤ G_{i} ≤ N$ for each valid $i$
the sum of $N$ over all test cases does not exceed $10^{6}$

------  Subtasks ------
Subtask #1 (50 points):
$1 ≤ N ≤ 50$
the sum of $N$ over all test cases does not exceed $500$

Subtask #2 (50 points): original constraints

----- Sample Input 1 ------ 
4

3

-1 0 -1

0 3 0 0

3

2 2 1

3 0 0 0

3

-1 2 -1

1 1 1 0

3

-1 2 2

0 1 1 0
----- Sample Output 1 ------ 
1 0 2

impossible

0 2 0

impossible

Source: codechef | Difficulty: VERY_HARD
Tags: Data structures

Mathematics

Greedy algorithms


Solutions:
def lower(x, b):
	l = 0
	h = len(b) - 1
	d = {}
	while l <= h:
		m = (l + h) // 2
		if b[m] == x:
			return m
		elif b[m] < x:
			l = m + 1
		elif b[m] > x:
			d[b[m]] = m
			h = m - 1
	k = len(d)
	if k > 0:
		mi = list(d.keys())
		p = mi[k - 1]
		return d[p]
	else:
		return None
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	g = list(map(int, input().split()))
	b1 = [0] * n
	if sum(g) != n:
		print('impossible')
		continue
	nocount = 0
	for i in range(n):
		if a[i] == -1:
			nocount += 1
		else:
			b1[a[i]] += 1
	k = n + 1
	b2 = []
	for i in range(k):
		b2.extend([i] * g[i])
	i = n - 1
	flag = 0
	key = []
	while i >= 0:
		l = lower(b1[i], b2)
		if l == None:
			flag = 1
			break
		diff = b2[l] - b1[i]
		key.extend([i] * diff)
		i -= 1
		b2.pop(l)
	k = len(key)
	if k != nocount:
		flag = 1
	if flag:
		print('impossible')
		continue
	else:
		temp = 0
		key.reverse()
		for i in range(n):
			if a[i] == -1:
				a[i] = key[temp]
				temp += 1
			print(a[i], end=' ')
		print()