The divisibility game

Two players, X and Y, play the following game.

• They are given a positive integer $P$ and a set $A = \{a_1, a_2, \ldots, a_N\}$ of $N$ distinct nonnegative integers. Every $a_i$ is less than $P$.
• The players take turns alternately. On each turn, the player to move deletes one number from $A$.
• After exactly $K$ turns, if the sum of the numbers remaining in $A$ is divisible by $P$, X wins. Otherwise, Y wins.

Write a program that determines who wins when both players play optimally.

The first line contains a positive integer $T$, the number of games in the input.

Then, for each $i = 0, 1, \ldots, T-1$:

• line $3i+2$ contains $N$, $K$, and $P$, separated by spaces;
• line $3i+3$ contains a single character, X or Y, which is the player who moves first;
• line $3i+4$ contains $a_1, a_2, \ldots, a_N$, separated by spaces.

Print one line with $T$ characters and no separators, one character per game. The $i$-th character is X if X wins the $i$-th game no matter how Y plays, and Y otherwise.

• $1 \le K \le N \le 5000$
• $P \le 10^{18}$
• $0 \le a_i < P$ for every $i$, and $a_i \ne a_j$ for every $i \ne j$