Description

 

Let's play Wordle!!!

You are given an answer string $S$ of length $n$ (all lower-case letters).

Then you will receive an integer $q$.

For each of the next $q$ lines, you are given a guess string $T$ of length $n$ (all lower-case letters).

For each guess, output a feedback string of length $n$ using the following symbols:

• G (Green): the letter matches the answer at the same position.
• Y (Yellow): the letter occurs in the answer but in a different position (respecting letter counts).
• B (Black): the letter does not occur in the answer in any unmatched position.

Important (duplicate letters):

A letter in the guess can only be marked G or Y as many times as it appears in the answer.

If the guess has extra occurrences beyond what the answer contains, the extra ones are marked B.

Example with abbey:

• Answer = abbey
• Guess = bobby

Step 1 (mark greens): positions 3 (b) and 5 (y) are exact matches → ??G?G.

Step 2 (check yellows with remaining letters, from left to right):

• Guess position 1 = b → still one b left in answer → mark Y.
• Guess position 2 = o → not in answer → mark B.
• Guess position 4 = b → no b left in answer → mark B.

Final result: YBGBG.

Input

• Line 1: a string $S$ — the hidden answer ($\lvert S \rvert = n$, lower-case a–z).
• Line 2: an integer $q$ — the number of guesses.
• Next $q$ lines: each line contains a string $T$  — the guess ($\lvert T \rvert = n$, lower-case a–z).

Constraints

• $1 \leq n \leq 2 \times 10^4$
• $1 \leq q \leq 50$

All strings consist only of lower-case English letters a–z.

Subtask

For testcases 1~5:

• $1 \leq n \leq 1000$

For testcases 6~10:

• No additional constraints.

Output

For each guess, output a line with a string of length $n$ over the alphabet {G, Y, B} indicating the feedback for that guess.

Sample Input  Download

Sample Output  Download

Tags

Discuss