시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.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..

Constraints

• 1 ≤ K ≤ N ≤ 5000;
• P ≤ 1018;
• 0 ≤ ai < P for each 0 ≤ i < N and ai ≠ aj for each 0 ≤ i < j < N.
• In 20% of the test cases N ≤ 25.
• In other 20% of the test cases P is a prime number.

## 출력

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

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