The game "Divisibility"#8567
Two players and play the following game:
They are given a positive integer and a set consisting of different nonnegative integers, A = \{a_1, a_2, \ldots, a_n\}, such that every a_i is less than .
Players play with alternating turns. Each player on his turn deletes a number from the set .
If after exactly turns, the sum of the numbers remaining in is divisible by - Player wins. Otherwise - Player wins.
Write a program, which determines who wins if both players play optimally.
On the first line there is the positive integer - the number of games in this test case.
After that, for each i = 0, 1, \ldots, t - 1:
on the (3i + 2)-nd line are the numbers , (1 \leq k \leq n \leq 5000) and (p \leq 10^{18});
on the (3i + 3)-rd line is either the symbol , or the symbol , denoting which of the players goes first;
on the (3i + 4)-th line are the space separated numbers a_1, a_2, \ldots, a_n (0 \leq a_i < p).
Print one line with symbols (without separators), one symbol for each game in the test case. The -th symbol should be , if wins in the -th game, no matter how plays; otherwise, this symbol should be .
Example 1