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

Два игрока 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.

Примеры