듀얼디스크 개발

강인! 무적! 최강!

— 카이바 세토, 「유희왕」

이 문제는 인터랙티브 문제입니다.

카이바 코퍼레이션은 듀얼 디스크를 개발하고 있다. 그 기능 중 하나는 카드를 셔플하는 것으로, 이는 몇 가지의 기본 셔플을 차례로 적용하여 원하는 목표 상태를 만들어 내는 방식으로 작동한다. 듀얼 디스크에는 카드가 총 $N$장 있으며, 초기 상태에서는 위에서부터 $i$번째 카드에 $i$가 적혀 있다.

당신은 $K$개 이하의 기본 셔플들을 원하는 대로 설계할 수 있다. 이중 $i$번 기본 셔플은 길이가 $N$인 순열 $P_i$로 나타내며, 이는 셔플 전 위에서부터 $j$번째 자리에 있던 카드가 셔플 후 위에서부터 $P_{i, j}$번째 자리로 이동하게 되는 셔플을 의미한다.

기본 셔플들을 설계한 후에는 설계한 기본 셔플들을 이용해서 만들어야 하는 목표 상태가 주어진다. 목표 상태는 길이가 $N$인 순열 $Q$로 나타내며, 위에서부터 $j$번째 카드에 $Q_j$가 적혀 있는 상태를 의미한다. 초기 상태에서부터 기본 셔플들 중 하나를 선택하여 적용하는 것을 $X$회 이하로 반복하여 주어진 목표 상태를 만들 수 있는 방법을 찾아야 한다. 목표 상태는 기본 셔플들을 확정한 후에 주어짐에 유의하라.

당신의 프로그램은 아래의 과정을 통해 표준입력과 표준출력으로 인터랙터와 상호작용해야 한다.

입력은 하나 이상의 테스트 케이스로 이루어져 있다. 처음에 한 번 기본 셔플들을 설계한 후, 이들을 이용해 모든 테스트 케이스의 목표 상태를 만들어야 한다.

첫 번째 줄에 세 정수 $N, K, X$가 공백을 사이에 두고 주어진다. $(2\leq N\leq 500;\; K=55;\; X=2500)$

이후 사용할 기본 셔플의 수 $K'$를 출력한다. $(1\leq K'\leq K)$

다음 $K'$개의 줄 중 $i$번째 줄에 $N$개의 정수 $P_{i, 1}, P_{i, 2}, \cdots, P_{i, N}$을 공백을 사이에 두고 출력한다.

다음 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스에 대해서 아래와 같이 상호작용해야 한다. $(1\leq T \leq 100)$

테스트 케이스의 첫 번째 줄에는 $N$개의 정수 $Q_1, Q_2, \cdots, Q_N$이 공백을 사이에 두고 주어진다.

다음 줄에 그 목표 상태를 만들기 위해 필요한 기본 셔플의 개수 $X'$를 출력한다. $(0\leq X'\leq X)$

다음 줄에 목표 상태를 만드는 데 사용한 기본 셔플들을 나타내는 $X'$개의 정수 $A_1, A_2, \cdots, A_{X'}$를 출력한다. 이는 초기 상태에서부터 순서대로 $i$번째에 $A_i$번 기본 셔플을 적용했을 때 목표 상태를 만들 수 있음을 나타낸다.

각 테스트 케이스는 독립적이다. 즉, 각 테스트 케이스가 끝날 때마다 디스크가 초기상태로 돌아간다.

또한 마지막이 아닌 테스트 케이스에 대한 상호 작용이 종료되었다면 즉시 다음 테스트 케이스에 대한 상호 작용으로 넘어가야 하고, 마지막 테스트 케이스에 대한 상호 작용이 종료되었다면 즉시 프로그램을 종료해야 한다.

각 채점 데이터에 대하여, 모든 테스트 케이스에서 제출한 답이 정답이라면 AC, 적어도 하나의 테스트 케이스에서 제출한 답이 오답이라면 WA 결과를 받는다. 단, 문제의 제한 안에 올바른 상호작용을 통해 답을 출력하지 못하면 예상치 못한 채점 결과를 받을 수 있다.

이 문제에서는, $X'$의 값에 따른 부분 점수가 주어진다.

각 채점 데이터에 대하여, 모든 테스트 케이스에서 출력한 $X'$의 최댓값을 $X_{\max}$라 하자. 모든 테스트 케이스에서 올바른 답을 출력했다면, 해당 채점 데이터의 점수는 다음과 같이 계산된다.

하나 이상의 테스트 케이스에서 잘못된 답을 출력하면 해당 채점 데이터의 점수는 $0$점이다.

당신의 프로그램은 무언가를 출력한 후 즉시 출력 버퍼를 비워야 한다. 다음은 언어별 출력 버퍼를 비우는 방법이다.

• C — fflush(stdout)
• C++ — std::cout.flush()
• Python — sys.stdout.flush()
• Java — System.out.flush()
• 그 외의 언어는 각 언어의 Documentation을 참고한다.