14058번 - The Game “Divisibility” 다국어

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 = {a₁, a₂, …, a_N}, such that every a_i 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 a₁, a₂, …, a_N..

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 ≤ 10¹⁸;
• 0 ≤ a_i < P for each 0 ≤ i < N and a_i ≠ a_j for each 0 ≤ i < j < N.