eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Игра "Делимость"

Игра "Делимость"

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Два игрока X и Y играют в следующую игру:

  • Имеется натуральное число p и множество A состоящее из n различных неотрицательных целых чисел, A = {a[1], a[2], ..., a[n]}, такое что каждое a[i] меньше p.

  • Игроки ходят по очереди. Каждый игрок удаляет одно число из множества A.

  • Если после в точности k раундов сумма оставшихся в A чисел делится на p - побеждает Игрок X. Иначе побеждает Игрок Y.

Напишите программу, которая определит кто победит, если оба игрока играют оптимально.

Вхідні дані

Первая строка содержит количество игр t.

Далее для каждого i = 0, 1, ..., t1:

  • на строке номер (3i + 2) расположены числа n, k (1kn5000) и p (p10^18);

  • на строке номер (3i + 3) расположен либо символ X, либо символ Y, указывающие кто из игроков ходит первым;

  • на строке номер (3i + 4) расположены числа a[1], a[2], ..., a[n] (0a[i] < p).

Вихідні дані

В одной строке выведите t символов (без разделителей), по одному символу для каждого теста. i-ым символом будет X, если X выигрывает в i-ой игре независимо от игры Y; иначе вывести символ 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
Джерело 2016 VIII International autumn tournament in informatics, Shumen, Senior, Задача B