멀티 플레이어 게임

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

브루와 민규는 서울과학고등학교에서 열리는 전략 서바이벌 게임 '더 챌린저스'에 팀으로 참가했다.

예선 게임은 두 팀원 중 한 명이 송신자, 다른 한 명이 수신자 역할을 맡아 게임을 진행한다. 게임이 진행되는 동안 두 팀원은 서로 다른 방에 들어가며 소통할 수 없다. 브루가 송신자, 민규가 수신자 역할을 맡는다.

게임의 딜러 동현은 먼저 브루의 방에 들어가 길이 $L$의 비트스트링 $S$('0'과 '1'로만 이루어진 문자열)를 제시한다. 이후 브루는 길이 $N$의 순열 $A$를 제출해야 한다. 동현은 브루가 제출한 순열을 다음과 같은 과정으로 섞는다.

• 먼저 순열 $A$의 수 중 하나를 피봇 $p$로 선택한다.
• 이후, $p$보다 작은 수는 원래 순열에 있는 순서대로 $p$ 왼쪽으로 옮기고, $p$보다 큰 수는 원래 순열에 있는 순서대로 $p$ 오른쪽으로 옮긴다. 이렇게 섞인 순열을 $A'$이라고 하자.

예를 들어, 원래 순열 $A=[3,6,1,5,4,2]$이고, 피봇 $p=4$라면, 섞인 순열 $A'=[3,1,2,4,6,5]$가 된다. 이후 동현은 민규에게 순열 $A'$를 전달한다. 민규가 이 순열 $A'$를 보고 비트스트링 $S$를 정확히 맞힌다면 게임에서 승리한다.

민규가 운 좋게 비트스트링 $S$를 정확히 맞히는 것을 방지하기 위해, 동현은 초기에 브루에게 $T$개의 비트스트링을 제시할 것이다. 그리고 브루가 제출한 $T$개의 순열 각각을 동현이 섞어 새로운 순열 $T$개를 만들고, 이 $T$개의 순열을 임의의 순서로 민규에게 전달할 것이다.

당연하게도, 브루와 민규는 게임이 시작되기 전 전략을 논의할 수 있다. 또한, 브루와 민규는 게임 전 $N$과 $L$의 값을 직접 정할 수 있다. $N$과 $L$의 값에 따라 게임의 난이도, 그리고 게임 승리 시 얻는 점수가 결정된다. 난이도가 쉽게 두 변수를 정하면 게임에서 승리할 수 있겠지만, 얻는 점수가 더 낮아질 것이다.

브루와 민규를 위해 게임에서 승리할 수 있는 최선의 전략을 만들어 주자.

• $R$은 brue 또는 mingyu
• $1\le T\le 1000$
• $S$는 길이 $L$의 문자열
• $S_i\in{\text{‘0'} ,\text{‘1'}}$ $(1\le i\le L)$
• $1\le N\le 60$
• $1\le L\le 210$
• $1\le A_i\le N$ $(1\le i\le N)$
• $A_i\neq A_j$ $(1\le i<j\le N)$

출력 버퍼를 비우는 방법은 다음과 같다.

• C: fflush(stdout)
• C++: std::cout << std::flush
• Java: System.out.flush()
• Python: sys.stdout.flush()

이외의 언어에 대해서는 언어별 명세를 참고해야 한다.