페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8143
서브태스크

구슬게임 필승법 1s 1024MB

문제

갑돌이와 갑순이는 구슬게임을 하고 있다. 게임의 규칙은 다음과 같다: 갑돌이와 갑순이는 각각 일정 수의 구슬을 가지고 시작한다. 갑돌이는 자신의 손에 A개의 구슬을 내밀고, 갑순이는 A가 짝수인지 홀수인지 맞춘다.

만약 갑순이가 맞추면, 그녀는 갑돌이에게서 A개의 구슬을 얻는다.

반대로 틀리면, 갑순이는 자신이 가진 구슬 A개를 잃고 갑돌이에게 준다. 만약 갑순이가 A개의 구슬보다 적게 가지고 있다면, 그녀는 남은 모든 구슬을 잃는다.

한 플레이어가 모든 구슬을 잃으면 패배한다.

몇 번의 턴이 지나고 난 후, 갑순이는 N개의 구슬을 가지고 있다. 그녀는 이기기 어렵다고 느끼지만, 패배하지 않으려고 게임을 계속하고 있다. 갑순이는 갑돌이의 습관을 잘 파악하여, 턴 i에서 갑돌이가 내미는 구슬의 개수가 K개의 서로 다른 값 중 하나라는 것을 알고 있다. 또한, 갑돌이는 M번의 턴이 지나면 지루해져서 게임을 멈춘다.

갑순이가 어떤 방식으로든 패배하지 않도록 보장할 수 있는 사전순으로 가장 작은 턴 시퀀스를 찾아야 한다.


입력

첫 번째 줄에는 테스트 케이스의 수 T (1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스는 다음과 같이 구성된다:

첫 번째 줄에는 세 정수 N, M, K가 주어지며, 각각 갑순이의 구슬 개수, 턴 수, 갑돌이가 선택할 수 있는 구슬 개수의 종류를 나타낸다.

다음 M개의 줄에는 각 줄마다 K개의 서로 다른 정수 a_{i,1}\ a_{i,2}\ ...\ a_{i,K}가 주어지며, 이는 턴 i에서 갑돌이가 내밀 수 있는 구슬의 수를 나타낸다.

[제약 조건]

  • 1 ≤ N ≤ 10^9

  • 1 \le M \le 3 \times 10^5

  • 1 \le K \le 4

  • 1 ≤ a_{i,j} ≤ 10^3

  • 모든 테스트 케이스에서 M의 총합은 최대 3 × 10^5임이 보장된다.


출력

각 테스트 케이스에 대해 갑순이가 패배하지 않도록 보장할 수 있는 사전순으로 가장 작은 "짝수" 또는 "홀수"의 턴 시퀀스를 출력하라. 만약 패배가 불가피하다면, -1을 출력하라. 각 결과는 한 줄에 출력되며, "짝수"는 "Even", "홀수"는 "Odd"로 표기한다.


부분문제

번호 점수 조건
#130점

M \le 16

#230점

M \le 1000

#340점

추가 제약 조건 없음


예제 #1

2
10 3 2
2 5
1 3
1 3
10 3 3
2 7 5
8 3 4
2 5 6
Even Even Odd
-1

첫 번째 테스트 케이스:
사전순으로 더 작은 시퀀스인 "Even Even Even"을 선택하면 갑돌이는 다음과 같은 방식으로 갑순이를 패배시킬 수 있다:

  • 5개의 구슬을 내밀어 갑순이의 구슬을 10에서 5로 줄인다.

  • 3개의 구슬을 내밀어 갑순이의 구슬을 5에서 2로 줄인다.

  • 다시 3개의 구슬을 내밀어 갑순이의 모든 구슬을 잃게 만든다.

그러나 "Even Even Odd"를 선택하면 갑순이가 마지막에 3개를 받을 수 있어 총 5개의 구슬을 유지할 수 있다.

두 번째 테스트 케이스:
갑순이가 어떤 시퀀스를 선택하더라도 갑돌이는 모든 구슬을 가져갈 수 있다.


예제 #2

1
20 8 2
3 5
3 5
3 5
3 5
3 5
3 5
3 5
3 5
Even Even Even Odd Even Odd Even Odd

출처

USACO 2024 February Silver 3번

로그인해야 코드를 작성할 수 있어요.