Description

Each problem that was WA has a score. To judge whether the degree of WA problems is the same for the two people, Xiao X uses the following method:

When bored, she came up with a magical function:

She believes that no matter what values $a_i$ take, if the sums of $f(x)$ over two groups are equal, then the error levels of the two groups of problems are very similar.

Suppose there are two modified sets of WA problems with scores $A=\{1,4,6,7 \}$ and $B=\{2,3,5,8\}$. When $a_1=a_2=a_3=1$, the magical function is:

Then $f(1)=3, f(2)=7, f(3)=13 \cdots$.

Obviously: $f(1) + f(4) + f(6) + f(7) = 124 = f(2) + f(3) + f(5) + f(8)$.

For this set of coefficients, this partition is valid. It can be proven that for any values of $a_i$, grouping according to the above scheme satisfies the condition (the sums of $f(x)$ over the two groups are the same). If you do not believe it, you can enumerate manually (#huaji).

So $A=\{1,4,6,7 \}, B=\{2,3,5,8\}$ is a valid grouping.

Input Format

The first line contains an integer $n$, meaning there are $2^n$ WA problems, with scores from $1$ to $2^n$, with $n \ge 2$.

The second line contains an integer $q$, indicating there are $q$ queries.

The last line contains $q$ integers, each asking whose name is on the WA problem with score $x$.

(Because Xiao X is relatively weak, we assume the WA problem with score $1$ belongs to her.)

Output Format

Output $q$ lines, each containing a character $\verb!X!$ or $\verb!Z!$, indicating whose signature is on the WA problem with score $x$.

3
2
4 5

X
Z

Hint

Constraints and Conventions

• For $10\%$ of the testdata, $2 \le n \le 4$, $q \le 10$.
• For $40\%$ of the testdata, $2 \le n \le 20$, $1 \le q \le 5000$.
• For $100\%$ of the testdata, $2 \le n \le 60$, $q \le 10^6$.

Translated by ChatGPT 5