Frequency Function

All submissions for this problem are available.
### Read problem statements in [Hindi](http://www.codechef.com/download/translated/LTIME79/hindi/FREQFUN.pdf),[Bengali](http://www.codechef.com/download/translated/LTIME79/bengali/FREQFUN.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/LTIME79/mandarin/FREQFUN.pdf), [Russian](http://www.codechef.com/download/translated/LTIME79/russian/FREQFUN.pdf), and [Vietnamese](http://www.codechef.com/download/translated/LTIME79/vietnamese/FREQFUN.pdf) as well. Chef had a sequence $S_0, S_1, \ldots, S_{N1}$; each element of this sequence was an integer between $0$ and $N1$ (inclusive). Unfortunately, he forgot some (possibly zero or all) elements of this sequence. You are given a sequence $A_0, A_1, \ldots, A_{N1}$, 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_{N1}$, 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$ spaceseparated integers $A_0, A_1, \ldots, A_{N1}$.  The third line contains $N+1$ spaceseparated 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$ spaceseparated integers $S_0, S_1, \ldots, S_{N1}$  the lexicographically smallest valid sequence $S$. ### Constraints  $1 \le T \le 1,000$  $2 \le N \le 10^5$  $1 \le A_i \le N1$ for each valid $i$  $0 \le G_i \le N$ for each valid $i$  the sum of $N$ over all test cases does not exceed $10^6$ ### Subtasks **Subtask #1 (50 points):**  $1 \le N \le 50$  the sum of $N$ over all test cases does not exceed $500$ **Subtask #2 (50 points):** original constraints ### Example Input ``` 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 ``` ### Example Output ``` 1 0 2 impossible 0 2 0 impossible ```Author:  kingofnumbers 
Editorial  https://discuss.codechef.com/problems/FREQFUN 
Tags  deadwing97, easymedium, greedy, kingofnumbers, ltime79 
Date Added:  27122019 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 