Problem Statement

One of the phrases often heard in Iwai Seijin's videos is "It's Warong Answer!" ("Warong Answer yanke!").
It is the phrase Iwai Seijin often shouts when, while solving competitive programming problems, the result of submitting code is WA (wrong answer).
The reading "Warong", far too unnatural as a katakana pronunciation of "wrong", has captured the hearts of many viewers and will not let go.

By the way, when code is tested on the sample cases and does not pass, Iwai Seijin often shouts "Why the heck!" ("Nande yanen!") and rarely shouts "It's Warong Answer!".
Also, when the result of submitting code is AC, he naturally never shouts "It's Warong Answer!".

With this in mind, solve the following problem.

You play a game called the Warong Answer Game with Takahashi.
The rules of the Warong Answer Game are as follows.

First, Takahashi has a string ${X}$ consisting only of A and W. You do not know ${X}$.

Next, Takahashi tells you strings ${R}$ and ${S}$ and an integer ${K}$.

${R}$ is the string obtained by replacing ${0}$ or more characters of ${X}$ with ?.

${S}$ is either Warong or NotWarong, and ${S}$ is Warong if and only if both of the following conditions are satisfied.

• The first ${K}$ characters of ${X}$ are all A.
• ${X}$ contains at least ${1}$ W.

Your winning condition in the Warong Answer Game is to answer with the string obtained by replacing, for every ${i\ (1 \leq i \leq |X|)}$ such that the ${i}$-th character of ${X}$ is determined, the ${i}$-th character of ${R}$ with the ${i}$-th character of ${X}$.
Here, for ${i\ (1 \leq i \leq |X|)}$, the ${i}$-th character of ${X}$ is said to be determined to be a character ${c}$ if, for every string ${x}$ satisfying the following condition, the ${i}$-th character of ${x}$ is ${c}$.

• Assuming that ${X}$ is ${x}$ does not contradict the rules of the Warong Answer Game described above.

Beat Takahashi in the Warong Answer Game.

You are given $T$ test cases; solve each of them.

Constraints

• ${1 \leq T \leq 2 \times 10^5}$
• ${R}$ is a string consisting only of A, W, and ?
• ${S}$ is Warong or NotWarong
• ${K}$ is an integer
• ${1 \leq K \leq |R|}$
• ${R,\ S,\ K}$ do not contradict the rules of the Warong Answer Game
• The sum of $|R|$ over all test cases is at most $2 \times 10^5$

Input

The input is given from Standard Input in the following format, where $\mathrm{case}_i$ denotes the $i$-th test case.

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

Each test case is given in the following format.

${R}$
${S}$
${K}$

Output

Print $T$ lines.
On the $i$-th line, print the string you must answer in order to beat Takahashi in the Warong Answer Game for the $i$-th test case.

Sample

3
A?W?A
Warong
2
????????
NotWarong
3
W
NotWarong
1

AAW?A
????????
W