마법 카드

Pak Dengklek은 마술을 선보이려고 한다. Pak Dengklek의 조수인 Pak Ganesh는 $1$부터 $N$까지 번호가 매겨진 $N$장의 카드를 가지고 있다. 관객 한 명을 무대로 초대하여 이 카드들 중 서로 다른 $K$장을 고른 뒤 Pak Ganesh에게 건네게 한다. Pak Ganesh는 카드를 확인한 다음 $K$장의 카드 중 한 장을 버리고, 남은 $K - 1$장의 카드를 임의의 순서로 탁자 위에 놓는다. 그런 다음 Pak Dengklek은 탁자 위의 $K - 1$장의 카드를 보고 Pak Ganesh가 버린 카드를 알아낼 수 있어야 한다.

당연히 마술이 시작된 뒤에는 Pak Dengklek과 Pak Ganesh가 서로 의사소통해서는 안 되지만, 마술이 시작되기 전에 전략을 정할 수는 있다. 이들의 전략을 설계하여 도와야 한다. 이번에는 Pak Dengklek과 Pak Ganesh가 동일한 $N$과 $K$의 값으로 이 마술을 $Q$번 수행한다.

구현 세부사항

다음 프로시저를 구현해야 한다.

void init_assistant(int N, int K)

• $N$: 마술에 사용되는 카드의 수.
• $K$: 관객이 고르는 카드의 수.
• 이 프로시저는 choose_cards가 호출되기 전에 정확히 한 번 호출된다.

int[] choose_cards(int[] cards)

• $cards$: 관객이 고른 카드 번호가 오름차순으로 들어 있는 길이 $K$의 배열.
• 이 프로시저는 Pak Ganesh가 탁자 위에 남긴 $K - 1$장의 카드를 그 순서와 함께 반환해야 한다. 모든 원소는 서로 달라야 하며 cards 배열에 존재해야 한다.
• 이 프로시저는 정확히 $Q$번 호출된다.

void init_magician(int N, int K)

• $N$: 마술에 사용되는 카드의 수.
• $K$: 관객이 고르는 카드의 수.
• 이 프로시저는 find_discarded_card가 호출되기 전에 정확히 한 번 호출된다.

int find_discarded_card(int[] cards)

• $cards$: 탁자 위에 놓인 카드 번호가 놓인 순서대로 들어 있는 길이 $K - 1$의 배열.
• 이 프로시저는 Pak Ganesh가 버린 카드의 번호를 반환해야 한다.
• 이 프로시저는 정확히 $Q$번 호출된다.

각 테스트 케이스는 하나의 $N$과 $K$ 상황으로 구성된다. 위 프로시저들을 호출하는 프로그램은 다음과 같이 정확히 두 번 실행된다.

프로그램의 첫 번째 실행에서는 다음과 같다.

• init_assistant는 choose_cards가 호출되기 전에 정확히 한 번 호출된다.
• choose_cards는 정확히 $Q$번 호출된다. 각 호출에서 반환된 선택 카드들은 채점 시스템에 저장된다.

프로그램의 두 번째 실행에서는 다음과 같다.

• init_magician은 find_discarded_card가 호출되기 전에 정확히 한 번 호출된다.
• find_discarded_card는 정확히 $Q$번 호출된다. 각 호출에서는 마술 수행 중 하나가 임의로 선택되며, choose_cards가 반환한 카드들이 find_discarded_card의 입력으로 사용된다.

특히 프로그램의 첫 번째 실행에서 정적 변수나 전역 변수에 저장한 어떠한 정보도 프로그램의 두 번째 실행에서는 사용할 수 없다.

예제

다음 호출을 살펴보자.

init_assistant(5, 3)

모든 마술에서 사용할 카드는 $5$장이며, 각 마술에서는 관객 한 명을 초대하여 서로 다른 카드 $3$장을 고르게 한다.

Pak Ganesh의 초기화가 완료된 뒤 다음 호출을 살펴보자.

choose_cards([1, 2, 3])

이는 관객이 번호가 $1$, $2$, $3$인 카드를 골랐다는 뜻이다. Pak Ganesh가 $1$번 카드를 버리고 탁자 위에 $3$번 카드를 $2$번 카드보다 앞에 놓았다고 가정하면, choose_cards는 $[3, 2]$를 반환해야 한다.

가능한 또 다른 호출을 살펴보자.

choose_cards([1, 3, 4])

이는 관객이 번호가 $1$, $3$, $4$인 카드를 골랐다는 뜻이다. Pak Ganesh가 $3$번 카드를 버리고 탁자 위에 $1$번 카드를 $4$번 카드보다 앞에 놓았다고 가정하면, choose_cards는 $[1, 4]$를 반환해야 한다.

Pak Ganesh가 모든 마술 수행에 대해 탁자 위에 카드를 놓았다고 가정하고 다음 호출을 살펴보자.

init_magician(5, 3)

Pak Ganesh에게 주어진 것과 동일한 $N$과 $K$의 정보가 Pak Dengklek에게 주어진다.

Pak Dengklek의 초기화가 완료된 뒤 다음 호출을 살펴보자.

find_discarded_card([1, 4])

이는 Pak Dengklek이 탁자 위에서 $1$번 카드와 $4$번 카드를 이 순서대로 본다는 뜻이다. 이 카드들은 choose_cards([1, 3, 4])의 반환값과 같다. 그 마술 수행에서 Pak Ganesh가 $3$번 카드를 버렸으므로 find_discarded_card는 $3$을 반환해야 한다.

또 다른 호출을 살펴보자.

find_discarded_card([3, 2])

이는 Pak Dengklek이 탁자 위에서 $3$번 카드와 $2$번 카드를 이 순서대로 본다는 뜻이다. 이 카드들은 choose_cards([1, 2, 3])의 반환값과 같다. 그 마술 수행에서 Pak Ganesh가 $1$번 카드를 버렸으므로 find_discarded_card는 $1$을 반환해야 한다.

제약 조건

• $2 \le K \le 8$
• $K \le N \le 10\;000$
• $1 \le Q \le 50\;000$

choose_cards의 각 호출에 대해 다음 조건이 성립한다.

• $1 \le cards[i] \le N$ ($0 \le i \le K - 1$인 각 $i$에 대해).
• $cards$의 모든 원소는 서로 다르다.

find_discarded_card의 각 호출에 대해 다음 조건이 성립한다.

• 주어지는 모든 입력은 choose_cards가 반환한 $Q$개의 모든 반환값과 같으며, 그 순서는 무작위이다.

서브태스크

1. (5점) $N \le 3$, $K = 2$
2. (11점) $N \le 5$, $K = 3$
3. (24점) $N \le 12$, $K = 6$
4. (60점) $K = 8$

샘플 그레이더는 다음 형식으로 입력을 읽는다.

• $1$번째 줄: $N \; K \; Q$
• $2 + i$번째 줄 ($0 \le i \le Q - 1$): 관객이 마술 수행 $i$에서 고른 $K$장의 카드가 오름차순으로 주어진다.

입력과 동일한 순서로 각 마술 수행에 대해, 마술이 올바르게 수행되었다면 샘플 그레이더는 Accepted: chosen_cards = <chosen_cards>; discarded_card = <discarded_card>를 출력한다. 여기서 <chosen_cards>는 choose_cards가 반환한 카드들이고 <discarded_card>는 find_discarded_card가 반환한 카드이다.

각 마술 수행에 대해, 마술이 올바르게 수행되지 않았다면 샘플 그레이더는 Wrong Answer: <MSG>를 출력한다. 여기서 <MSG>는 다음 중 하나이다.

• invalid number of chosen cards: chosen_cards가 반환한 카드의 수가 올바르지 않다.
• invalid chosen card number: chosen_cards가 반환한 카드 번호 중 하나라도 올바르지 않다.
• duplicated chosen cards: chosen_cards가 반환한 카드 중 번호가 같은 두 카드가 존재한다.
• wrong discarded card: find_discarded_card가 반환한 카드가 올바르지 않다.