Access Globe has several increasing sequences of positive integers. He wrote down the decimal representation (without leading zeros) of each positive integer in these sequences, separating adjacent integers with a comma ,. Access Globe treats this sequence as a string consisting of digits 0-9 and commas ,, and stores these strings in a Trie. You do not need to know what a Trie 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 has a character, and the string formed by concatenating the characters on the edges along the path from the root to any leaf node is one of the increasing positive integer sequences he wrote down.

Cute little Tommy decided to tamper with this Trie. He first deleted the characters on some edges of the Trie and then filled in other characters. To avoid being discovered, Tommy must ensure that the modified Trie still satisfies the aforementioned property: the string formed by concatenating the characters on the edges along the path from the root to each leaf node is an increasing sequence of positive integers, and each positive integer has no leading zeros.

Now that Tommy has deleted characters on some edges, please help him complete the "filling in characters" operation. If there are multiple solutions, output the one that is lexicographically smallest.

Input

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

The first line contains a string of length $n$ consisting only of 0 through 9, ,, and ?. The $i$-th character represents the character on the edge connecting node $i$ to its parent, where ? indicates that the character on this edge has been deleted.

The second line contains $n$ integers, where the $i$-th integer represents the parent node $f_i$ of node $i$, with the guarantee that $0 \le f_i < i$.

Output

Output $T$ lines. For each test case, output a string of length $n$ representing the characters of each node in the lexicographically smallest way to fill in the question marks, where the $i$-th character corresponds to the character on the edge connecting node $i$ to its parent.

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

Examples

Input 1

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

Output 1

2,13,207104420026411

Note 1

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

Examples 2

See trie/trie2.in and trie/trie2.ans in the contestant directory.

Subtasks

For 20% of the data, $T \le 10$, and for each test case $n \le 80$, with no more than 8 ? characters. For another 10% of the data, $T \le 20$, and for each test case $n \le 80$, $f_i = i - 1$. For another 20% of the data, $f_i = i - 1$. For another 10% of the data, $n \le 80$. For all data, $T \le 100$, and for each test case $n \le 200$.

Note

The ASCII code of , is 44, which is smaller than all digits.