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 $S$ be the unfinished spell that was written on the wall. $S$ may contain lowercase English letters and “$?$” symbol. You will also be given $K$ missing letters. Each of the “$?$” symbols must be replaced by one or more letters from the $K$ 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 $S$ = $\textbf{c?b?b}$ ,
$K$ = $2$ and $2$ missing letters are $\textbf{ae}$.

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

Again if $S$ = $\textbf{?cde}$,
$K$ = $3$ and $3$ missing letters are $\textbf{baa}$.

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

Input

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

In each testcase, the first line will contain the string $S$. There will be atleast one “$?$” in the string.

The next line will contain an integer $K$ followed by $K$ lowercase English letters. The value of $K$ will not be less than the number of “$?$” in string $S$.

Constraints

Subtask 1 (15 Points)

$1 \leq T \leq 1000$

$K \leq 10$

The length of each string $S$ will not exceed $10$.

Subtask 2 (35 Points)

$1 \leq T \leq 100$

$K \leq 100$

The length of each string $S$ will not exceed $100$.

Subtask 3 (50 Points)

$1 \leq T \leq 500$

$K \leq 20000$

The length of each string $S$ will not exceed $20000$.

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 $A$ and $B$ of the same length then $A$ is lexicographically smaller than $B$ if there is a position $i$ such that $A_1$=$B_1$, $A_2$=$B_2$,…, $A_{i-1}$=$B_{i-1}$ and $A_i$<$B_i$.

Discussion

Statistics


18% Solution Ratio

riyad000Earliest, 3w ago

mahadi97Fastest, 0.2s

riyad000Lightest, 19 MB

niloycbShortest, 1174B

Submit

Login to submit