마법 카드 (어려움)

마술사 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가 소통할 수 없지만, 마술을 시작하기 전에 전략을 미리 정할 수 있다. 여러분이 두 사람의 전략을 설계해 도와야 한다. 이번에는 같은 N과 K 값으로 마술을 Q번 진행한다.

• $2 ≤ K ≤ 8$
• $K ≤ N$
• 주어진 $N$과 $K$에 대해 마술사와 조수의 전략이 존재한다
• $1 ≤ Q ≤ 50\,000$

choose_cards가 호출될 때마다:

• $0 ≤ i ≤ K - 1$인 모든 $i$에 대해 $1 ≤ cards[i] ≤ N$이다.
• cards의 모든 원소는 서로 다르다.

find_discarded_card가 호출될 때마다:

• 주어지는 모든 입력은 choose_cards가 Q번 반환한 값과 같고, 순서만 무작위로 섞여 있다.