Broken Device 2

Anna and Bruno are gamble masters. They play a game with D-taro, the dealer of the game.

In this game, Anna and Bruno stay in different rooms. They can communicate only through a broken device. D-taro gives an integer to Anna. Their goal is to send the given integer from Anna to Bruno through the device.

When the game starts, Anna declares an integer $m$ between 1 and 2000, inclusive. Then they play $Q$ rounds. Round $i$ ($1 \le i \le Q$) goes as follows.

1. D-taro gives an integer $A_i$ to Anna.
2. Anna inputs arrays $s_i$ and $t_i$ into the device. Every element of $s_i$ and $t_i$ is either 0 or 1. The two arrays have the same length, which is between 1 and $m$, inclusive.
3. Let $u_i$ be the array obtained from $s_i$ and $t_i$ by a riffle shuffle (see below). The device sends $u_i$ to Bruno.
4. Bruno sends an integer to D-taro. If this integer equals $A_i$, Anna and Bruno win the round.

Write programs that implement the strategies of Anna and Bruno so that they win all $Q$ rounds.

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

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