Magic Cards (Hard)

Pak Dengklek will perform a magic trick. His assistant, Pak Ganesh, has $N$ cards numbered from $1$ to $N$. A spectator comes to the stage, picks $K$ distinct cards, and gives them to Pak Ganesh. Pak Ganesh looks at the cards, discards one of the $K$, and leaves the remaining $K - 1$ cards on the table in any order. Pak Dengklek then looks at those $K - 1$ cards and must determine the discarded card.

Pak Dengklek and Pak Ganesh cannot communicate once the trick starts, but they can agree on a strategy beforehand. Design that strategy for them. This time, they will perform the trick $Q$ times with the same $N$ and $K$.

• $2 ≤ K ≤ 8$
• $K ≤ N$
• A strategy for the magician and the assistant exists for the given $N$ and $K$
• $1 ≤ Q ≤ 50\,000$

For each call to choose_cards:

• $1 ≤ cards[i] ≤ N$ for every $i$ such that $0 ≤ i ≤ K - 1$.
• All the elements of cards are distinct.

For each call to find_discarded_card:

• All the inputs given are the same as the $Q$ return values of choose_cards, in random order.