P3949 Wrong Answer

**This problem may not have a unique solution; the current problem and solution are for reference only.** Xiao X is not very good (she? tan 90°) and has many problems that were WA, so she feels upset. Xiao Z decides to comfort her, but there is not a single WA in his submission history (flag). So he decides to alter the signature of half of the problems, making Xiao X feel that their wrong problems are comparable, so she will feel better. 

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: $$f(x)=a_1x^0+a_2x^1+a_3x^2+\cdots+a_{n}x^{n-1}$$ 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: $$f(x)=x^2+x+1$$ 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.

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 $q$ lines, each containing a character $\verb!X!$ or $\verb!Z!$, indicating whose signature is on the WA problem with score $x$.

### 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