Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

The Hidden Island

By fsshakkhor · Limits 1s, 512 MB

It is believed that the hidden island of TreasureLand has many unsolved mysteries and undiscovered treasures. Captain Jack, along with his team found the hidden island. After roaming on the island for a few days, he found a closed cave over the mountain. He believed that the hidden treasure was inside the cave. On the cave wall, it was written "Saying the magical spell will open the cave door". The spell was also written there, but he could not read it because some letters were missing. He tried to guess the missing letters but failed. Being disappointed he looked down and found some letters written on the ground. Putting the letters in missing places of the spell, he completed the spell and the cave door opened. Let's see if you can complete it too or not.

Let SS be the unfinished spell that was written on the wall. SS may contain lowercase English letters and "??" symbol. You will also be given KK missing letters. Each of the "??" symbols must be replaced by one or more letters from the KK missing letters. Also, all the missing letters must be used. As there can be several possible ways to form the spell, we want to know the lexicographically smallest one.

For example,
if SS = c?b?b\textbf{c?b?b} ,
KK = 22 and 22 missing letters are ae\textbf{ae}.

The spell can be either cabeb\textbf{cabeb} or cebab\textbf{cebab}. Out of them cabeb\textbf{cabeb} is lexicographically smaller.

Again if SS = ?cde\textbf{?cde},
KK = 33 and 33 missing letters are baa\textbf{baa}.

The spell can be either aabcde\textbf{aabcde} or abacde\textbf{abacde} or baacde\textbf{baacde}. Out of them aabcde\textbf{aabcde} is lexicographically smallest.

Input

The first line will contain an integer TT denoting the number of testcases.

In each testcase, the first line will contain the string SS. There will be atleast one "??" in the string.

The next line will contain an integer KK followed by KK lowercase English letters. The value of KK will not be less than the number of "??" in string SS.

Constraints

Subtask 1 (15 Points)

1T10001 \leq T \leq 1000

K10K \leq 10

The length of each string SS will not exceed 1010.

Subtask 2 (35 Points)

1T1001 \leq T \leq 100

K100K \leq 100

The length of each string SS will not exceed 100100.

Subtask 3 (50 Points)

1T5001 \leq T \leq 500

K20000K \leq 20000

The length of each string SS will not exceed 2000020000.

Output

For each test case, print the spell in a new line.

Sample

InputOutput
5
t?ph
1 o
?in?o
2 gb
?ouris?
2 tt
?cde
2 ab
??cde
2 ab
toph
bingo
tourist
abcde
abcde

If we have two strings AA and BB of the same length then AA is lexicographically smaller than BB if there is a position ii such that A1A_1=B1B_1, A2A_2=B2B_2,..., Ai1A_{i-1}=Bi1B_{i-1} and AiA_i<BiB_i.

Discussion

Toph uses cookies. By continuing you agree to our Cookie Policy.