Lockpicking

The Hungarian State Treasury replaced the locking mechanism on one of their safes. This new lock can only be opened by custom keycards. The verification of a keycard follows a special protocol.

The lock has $N$ internal states numbered from $0$ to $N - 1$. For each $i$ from $0$ to $N - 1$, inclusive, there is a bit $A[i]$, and there are two states $S[i][0]$ and $S[i][1]$ associated with state $i$. A bit is a binary digit that is either $0$ or $1$. States $S[i][0]$ and $S[i][1]$ may coincide, and a state may be associated with itself.

Similarly, a keycard has $M$ states numbered from $0$ to $M - 1$. For each $j$ from $0$ to $M - 1$, bit $B[j]$ and states $T[j][0]$ and $T[j][1]$ are associated with state $j$. Hereafter, lock states and keycard states are both referred to as states.

In the verification process, the lock is paired with a keycard. Both of them can output bits and read the bits output by the other. At the start of the process, the lock is set to a specific initial state $i_0$. The keycard is also set to its own initial state $j_0$. They repeat the following steps at most $10^7$ times:

1. Each of them outputs a single bit according to its current state. If the lock is in state $i$, it outputs the bit $A[i]$. Analogously, the keycard outputs $B[j]$ if it is in state $j$.
2. They read the bit that the other one output. The lock reads $B[j]$, and the keycard reads $A[i]$. If the two bits differ, they register an error.
3. The devices change state based on the bit they read and the states associated with the current one. The lock enters state $S[i][B[j]]$, and the keycard enters state $T[j][A[i]]$.

If the number of errors ever reaches $K$, the verification fails and the process terminates. Otherwise, if they complete $10^7$ iterations without registering at least $K$ errors, the verification succeeds and the lock opens.

When the lock was installed, the mechanics forgot to specify the initial state $i_0$. As a result, whenever the lock is paired with a keycard, it starts in an arbitrary, unknown initial state.

Your task is to construct a keycard that can open the lock despite this mistake.

• $2 \le N \le 150$
• $0 \le A[i] \le 1$ (for each $i$ such that $0 \le i < N$)
• $0 \le S[i][0] < N$ and $0 \le S[i][1] < N$ (for each $i$ such that $0 \le i < N$)
• $1 \le M \le 50\,000$
• $0 \le B[j] \le 1$ (for each $j$ such that $0 \le j < M$)
• $0 \le T[j][0] < M$ and $0 \le T[j][1] < M$ (for each $j$ such that $0 \le j < M$)
• $K = N$