Гра "Ділимість"

Два гравці 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.

Приклади