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[1]
, a[2]
, ..., 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, which determines who wins if both players play optimally.
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 ≤ 10^18
);
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[1]
, a[2]
, ..., a[n]
(0 ≤ a[i]
< p).
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.