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