Broken Device 2

Anna와 Bruno는 도박의 달인이다. 두 사람은 게임의 진행자인 D-taro와 함께 게임을 한다.

이 게임에서 Anna와 Bruno는 서로 다른 방에 있다. 두 사람은 고장 난 장치로만 소통할 수 있다. D-taro는 Anna에게 정수 하나를 준다. 두 사람의 목표는 이 정수를 장치를 이용해 Anna에서 Bruno로 전달하는 것이다.

게임이 시작되면 먼저 Anna가 1 이상 2000 이하의 정수 $m$을 정한다. 이후 두 사람은 $Q$라운드를 진행한다. $i$번째 라운드($1 \le i \le Q$)는 다음과 같다.

1. D-taro가 정수 $A_i$를 Anna에게 준다.
2. Anna가 배열 $s_i$와 $t_i$를 장치에 입력한다. $s_i$와 $t_i$의 모든 원소는 0 또는 1이다. 두 배열의 길이는 같고, 그 길이는 1 이상 $m$ 이하이다.
3. $s_i$와 $t_i$로부터 리플 셔플(아래 정의 참고)로 얻은 배열을 $u_i$라 하자. 장치는 $u_i$를 Bruno에게 보낸다.
4. Bruno가 정수 하나를 D-taro에게 보낸다. 이 정수가 $A_i$와 같으면 이번 라운드는 두 사람의 승리이다.

모든 $Q$라운드에서 두 사람이 이기도록 Anna와 Bruno의 전략을 구현하는 프로그램을 작성하라.

$1 \le Q \le 1\,000$.

$1 \le A_i \le 10^{18}$ ($1 \le i \le Q$).