셔플

임리리는 애니메이션을 좋아하고, 최근 Amazon에서 Umaru의 시즌 전편을 샀다. Umaru의 $N$개 에피소드는 $N$장의 CD 세트로 제공되며, CD마다 에피소드가 하나씩 들어 있다. CD에는 $1, \ldots, N$의 라벨이 붙어 있고, 에피소드에도 $1, \ldots, N$의 번호가 매겨져 있다. 시청을 시작하려던 그녀는 제조 결함 때문에 에피소드 번호와 CD 라벨이 맞지 않는다는 것을 알았다. 그녀가 Amazon에 문의하자, CD 라벨은 에피소드 번호와 맞지 않지만 에피소드는 섞여 있을 뿐이고 세트에서 빠진 에피소드는 하나도 없다는 답변이 왔다. 스포일러를 피하려고 임리리는 직접 CD를 재생해 각 CD에 든 에피소드를 알아내고 싶지 않다. 그래서 친구 고양이 Rar에게 도움을 청한다. 절차는 다음과 같다. 임리리는 CD를 $K$장씩 $B$개의 상자에 나눠 담는다 ($N = B \times K$). 상자는 Rar에게 보내진다. 운송 중에 각 상자 안의 CD 순서가 바뀔 수 있고, 상자의 도착 순서도 바뀔 수 있다. Rar는 자신의 CD 플레이어로 CD를 재생하고, 각 상자에서 찾은 에피소드 집합을 적는다. 이 정보를 $B$장의 종이에 나눠 임리리에게 돌려보내며, 각 종이에는 상자 하나에 든 에피소드 번호 $K$개가 적혀 있다. 그다음 $N$장의 CD 전체가 임리리에게 돌아온다. 이 절차는 최대 $Q$번까지 수행할 수 있고, 그 뒤에는 Rar가 짜증을 내며 도움을 그만둔다. Rar의 도움을 최소한으로 받아 각 CD에 든 에피소드 번호를 구하라.

$B, K \ge 2$, $N \ge 6$, $N = B \times K$.

$N = 6$, $B = 3$, $K = 2$, $Q = 100$이고 테스트케이스가 서브태스크 2에 속한다고 하자. 에피소드는 $[3, 1, 4, 5, 2, 6]$이다. 함수는 solve(6, 3, 2, 100, 2)로 호출된다. 가능한 상호작용은 다음과 같다. shuffle([[1, 2], [3, 4], [5, 6]]) = [[6, 2], [5, 4], [3, 1]]. 상자 순서와 각 상자 안의 CD 순서가 뒤섞여 있으므로 Rar는 [[6, 5], [4, 3], [1, 2]]로 상자를 받고 [[6, 2], [5, 4], [3, 1]]을 보고한다. 이어서 shuffle([[2, 6], [3, 1], [5, 4]]) = [[6, 1], [2, 5], [4, 3]]에서는 상자가 뒤섞여 있고, Rar는 [[6, 1], [2, 5], [4, 3]]을 보고한다. 그다음 shuffle([[6, 5], [4, 2], [3, 1]]) = [[5, 1], [3, 4], [2, 6]]이다. 프로그램은 정보가 충분하다고 판단하고 에피소드가 $[3, 4, 1, 5, 2, 6]$이라고 결론 내려, $[3, 4, 1, 5, 2, 6]$을 반환한다. 에피소드가 맞고 질의를 100회 미만으로 썼으므로 이 테스트케이스는 정답으로 처리된다.