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 be the unfinished spell that was written on the wall. may contain lowercase English letters and "" symbol. You will also be given missing letters. Each of the "" symbols must be replaced by one or more letters from the 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, and 2 missing letters are .
The spell can be either or . Out of them is lexicographically smaller.
Again if , and 3 missing letters are .
The spell can be either or or . Out of them is lexicographically smallest.
The first line will contain an integer denoting the number of testcases.
In each testcase, the first line will contain the string . There will be atleast one "" in the string.
The next line will contain an integer followed by lowercase English letters. The value of will not be less than the number of "" in string .
The length of each string will not exceed 10.
The length of each string will not exceed 100.
The length of each string will not exceed 20000.
For each test case, print the spell in a new line.
Input | Output |
---|---|
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 and of the same length then is lexicographically smaller than if there is a position such that , , ..., and .