Description

Access Globe has several strictly increasing sequences of positive integers. He writes down the decimal representation (without leading zeros) of each positive integer in these sequences in order, separating every two adjacent integers with a comma ,. Access Globe treats each such sequence as a string consisting of digits $0 \sim 9$ and commas ,, and then stores these strings in a Trie. You do not need to know what a Trie actually is. You only need to know that the Trie obtained by Access Globe is a rooted tree with node $0$ as the root, each edge labeled with a character, and for every path from the root to a leaf, the characters on the edges along the path, concatenated in order, form one of the strictly increasing positive integer sequences he wrote down.

Cute little Tommy decides to tamper with this Trie. He first deletes the characters on some edges of the Trie, and then fills in some other characters. To avoid being discovered, Tommy must ensure that the modified Trie still satisfies the property above: for every path from the root to a leaf, the characters on the edges along the path, concatenated in order, form a strictly increasing sequence of positive integers, and each positive integer has no leading zeros.

Now Tommy has already deleted the characters on some edges. Please help him complete the “fill in characters” operation. If there are multiple solutions, output the lexicographically smallest one.

Input Format

The input file contains multiple test cases. The first line of the file is an integer $T$, which indicates the number of test cases. For each test case:

The first line contains a string of length $n$ consisting only of 0 to 9, ,, and ?. The $i$-th character represents the character on the edge connecting node $i$ and its parent. ? means that the character on this edge has been deleted.
The second line contains $n$ integers. The $i$-th integer represents the parent node $f_i$ of node $i$. It is guaranteed that $0 \le f_i < i$.

Output Format

Output $T$ lines. For each test case, output a string of length $n$, representing, among all ways to fill in the question marks, the lexicographically smallest one. The $i$-th character represents the character of node $i$.

If there is no valid way to fill in the characters, output failed.

1
2,?3,2?71?4420?2641?
0 1 2 3 4 5 6 7 8 6 10 7 4 4 14 3 2 1 1 0

2,13,207104420026411

Hint

Sample Explanation

The Trie filled in by Tommy is shown in the figure below. The red nodes are all leaf nodes. Note that the root node is at the lower left.

Constraints

For $20\%$ of the testdata, $T \le 10$, and for each test case $n \le 80$, with the number of ? not exceeding $8$;
For another $10\%$ of the testdata, $T \le 20$, and for each test case $n \le 80$, $f_i = i - 1$;
For another $20\%$ of the testdata, $f_i = i - 1$;
For another $10\%$ of the testdata, $n \le 80$;
For all testdata, $T \le 100$, and for each test case $n \le 200$.

Translated by ChatGPT 5