Гра "Ділимість"#8567
Два гравці і грають у таку гру:
Є натуральне число та множина , що складається з різних невід'ємних цілих чисел, A = \{a_1, a_2, \ldots, a_n\}, причому кожне a_i менше .
Гравці ходять по черзі. Кожен гравець видаляє одне число з множини .
Якщо після точно раундів сума чисел, що залишилися в , ділиться на , перемагає Гравець . Інакше перемагає Гравець .
Напишіть програму, яка визначить, хто переможе, якщо обидва гравці грають оптимально.
Перша строка містить кількість ігор .
Далі для кожного i = 0, 1, \ldots, t - 1:
у рядку номер (3i + 2) розташовані числа , (1 \leq k \leq n \leq 5000) та (p \leq 10^{18});
у рядку номер (3i + 3) розташований або символ , або символ , що вказують, хто з гравців ходить першим;
у рядку номер (3i + 4) розташовані числа a_1, a_2, \ldots, a_n (0 \leq a_i < p).
В одному рядку виведіть символів (без роздільників), по одному символу для кожного тесту. -им символом буде , якщо виграє в -ій грі незалежно від гри ; інакше виведіть символ .
Приклад 1