Два игрока 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, ..., t – 1:
на строке номер (3i + 2) расположены числа n, k (1 ≤ k ≤ n ≤ 5000) и p (p ≤ 10^18
);
на строке номер (3i + 3) расположен либо символ X, либо символ Y, указывающие кто из игроков ходит первым;
на строке номер (3i + 4) расположены числа a[1]
, a[2]
, ..., a[n]
(0 ≤ a[i]
< p).
В одной строке выведите t символов (без разделителей), по одному символу для каждого теста. i-ым символом будет X, если X выигрывает в i-ой игре независимо от игры Y; иначе вывести символ Y.