The game "Divisibility"
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 = {
a1,a2, ...,an}, such that everyaiis 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, which determines who wins if both players play optimally.
Input
On the first line there 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 (1 ≤ k ≤ n ≤ 5000) and p (p ≤
1018);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(0 ≤ai< p).
Output
Print 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.
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
XYX