듀얼디스크 개발

강인! 무적! 최강!

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

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

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

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

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

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

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

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

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

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

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

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