나누어떨어짐 게임

두 명의 플레이어가 번갈아 집합에서 수를 지울 때, 정확히 K번 지운 뒤 남은 합이 P로 나누어떨어지도록 X가 강제할 수 있는지 판정한다.

어려움8게임 이론조합론수학아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제 설명

예제1

두 사람 X와 Y가 다음 게임을 한다.

양의 정수 $P$ 와 서로 다른 음이 아닌 정수 $N$ 개로 이루어진 집합 $A = \{a_1, a_2, \ldots, a_N\}$ 이 주어진다. 모든 $a_i$ 는 $P$ 보다 작다.
두 사람은 번갈아 차례를 진행한다. 자기 차례가 된 사람은 집합 $A$ 에서 수 하나를 지운다.
정확히 $K$ 번의 차례가 끝났을 때 $A$ 에 남은 수의 합이 $P$ 로 나누어떨어지면 X가 이기고, 그렇지 않으면 Y가 이긴다.

두 사람이 모두 최선을 다할 때 누가 이기는지 구하는 프로그램을 작성하시오.

첫째 줄에 이 입력에 들어 있는 게임의 수를 나타내는 양의 정수 $T$ 가 주어진다.

그다음 $i = 0, 1, \ldots, T-1$ 에 대해 다음이 차례로 주어진다.

게임마다 문자 하나씩, 모두 $T$ 개의 문자를 구분자 없이 한 줄에 출력한다. $i$ 번째 문자는 $i$ 번째 게임에서 Y가 어떻게 두든 X가 이길 수 있으면 X, 그렇지 않으면 Y이다.