Recording and Querying Star's Phrases

You are given a list of n phrases which are repeated in order infinitely. Each phrase is either a normal string or the command CapsLock. The command CapsLock toggles a state that affects how subsequent strings are recorded:

• Initially, the toggle is off.
• When the toggle is on, each letter in a non-command string is transformed by swapping its case (lowercase becomes uppercase and vice versa).
• The command itself is not recorded.
• The toggle remains in its current state until a CapsLock command is encountered, at which point the toggle is flipped.

The phrases are repeated in the same order indefinitely. You are also given q queries. Each query provides a positive integer x, and you must output the x-th recorded phrase (i.e. skipping any occurrence of the command CapsLock).

Note: The effect of CapsLock persists across repetitions of the phrase list. In other words, the final toggle state after one cycle affects the transformation of phrases in the next cycle. If the toggle state at the end of a cycle is the same as at the beginning, then the recorded sequence per cycle is identical; otherwise, the recording pattern alternates every cycle.

The formulas used in this problem can be summarized as follows:

Let \(n\) be the number of phrases, and let the command be represented by CapsLock. For a phrase \(s\), if the current toggle state is true, then the recorded string is given by \[ \text{record}(s)=\text{swap}(s), \] where \(\text{swap}(s)\) converts every lowercase letter to uppercase and every uppercase letter to lowercase. Otherwise (if the toggle is off), it is recorded as \(s\) itself.

inputFormat

The first line contains two integers \(n\) and \(q\) (\(1 \leq n, q \leq 10^5\)).

The next \(n\) lines each contain a non-empty string. Each string is either a command CapsLock or a normal phrase consisting of English letters.

The following \(q\) lines each contain a single integer \(x\) (\(1 \leq x \leq 10^{12}\)), representing a query for the \(x\)-th recorded phrase.

outputFormat

For each query, output the corresponding recorded phrase on a new line.

sample

3 3
Hello
CapsLock
World
1
3
4

Hello
Hello
wORLD