시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB21150.000%

문제

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

• They are given a positive integer P and a set A consisting of N different nonnegative integers, A = {a1, a2, …, aN}, such that every ai is less than P.
• Players play with alternating turns. Each player on his turn deletes a number from the set A.
• If after exactly K turns, the sum of the numbers remaining in A is divisible by P – Player X wins. Otherwise – Player Y wins.

Write a program div, which determines who wins if both players play optimally.

입력

On the first line of the standard input is the positive integer T – the number of games in this test case.

After that, for each i = 0, 1, …, T – 1:

• on the (3i + 2)-nd line are the numbers N, K and P, separated by spaces;
• on the (3i + 3)-rd line is either the symbol X, or the symbol Y, denoting which of the players goes first;
• on the (3i + 4)-th line are the space separated numbers a1, a2, …, aN..

출력

The standard output should be one line with T symbols (without separators), one symbol for each game in the test case. The i-th symbol should be X, if X wins in the i-th game, no matter how Y plays; otherwise, this symbol should be Y.

제한

• 1 ≤ K ≤ N ≤ 5000;
• P ≤ 1018;
• 0 ≤ ai < P for each 0 ≤ i < N and ai ≠ aj for each 0 ≤ i < j < N.

예제 입력 1

3
5 3 7
X
1 2 3 4 6
8 4 13
Y
5 10 6 11 2 8 9 3
6 1 12
X
1 4 5 7 9 11


예제 출력 1

XYX