자물쇠 따기

헝가리 국고청은 금고 가운데 하나의 잠금 장치를 교체했다. 새 자물쇠는 전용 키카드로만 열 수 있다. 키카드의 검증은 특별한 프로토콜을 따른다.

자물쇠에는 0부터 $N - 1$까지 번호가 붙은 $N$개의 내부 상태가 있다. 0 이상 $N - 1$ 이하의 각 $i$에 대해 비트 $A[i]$가 있고, 상태 $i$에는 두 상태 $S[i][0]$과 $S[i][1]$이 대응한다. 비트는 0 또는 1인 이진 숫자다. $S[i][0]$과 $S[i][1]$은 같을 수 있으며, 상태가 자기 자신과 대응할 수도 있다.

마찬가지로 키카드에는 0부터 $M - 1$까지 번호가 붙은 $M$개의 상태가 있다. 각 $j$에 대해 비트 $B[j]$와 상태 $T[j][0]$, $T[j][1]$이 대응한다. 이하에서는 자물쇠의 상태와 키카드의 상태를 모두 상태라고 부른다.

검증 과정에서 자물쇠는 키카드와 짝을 이룬다. 두 장치는 모두 비트를 출력할 수 있고, 상대가 출력한 비트를 읽을 수 있다. 과정이 시작될 때 자물쇠는 정해진 초기 상태 $i_0$에 놓인다. 키카드도 자신의 초기 상태 $j_0$에 놓인다. 두 장치는 다음 단계를 최대 $10^7$번 반복한다.

1. 각 장치는 현재 상태에 따라 비트 하나를 출력한다. 자물쇠가 상태 $i$에 있으면 비트 $A[i]$를 출력한다. 마찬가지로 키카드가 상태 $j$에 있으면 $B[j]$를 출력한다.
2. 두 장치는 상대가 출력한 비트를 읽는다. 자물쇠는 $B[j]$를 읽고, 키카드는 $A[i]$를 읽는다. 두 비트가 다르면 오류를 한 번 기록한다.
3. 두 장치는 읽은 비트와 현재 상태에 대응하는 상태에 따라 상태를 바꾼다. 자물쇠는 상태 $S[i][B[j]]$로 들어가고, 키카드는 상태 $T[j][A[i]]$로 들어간다.

오류 횟수가 $K$에 도달하면 검증은 실패하고 과정은 종료된다. 오류를 $K$번 이상 기록하지 않고 $10^7$번의 반복을 모두 마치면 검증에 성공하여 자물쇠가 열린다.

자물쇠를 설치할 때 기계 담당자가 초기 상태 $i_0$를 지정하지 않았다. 그래서 자물쇠가 키카드와 짝을 이룰 때마다 자물쇠는 임의의 알 수 없는 초기 상태에서 시작한다.

이 실수에도 불구하고 자물쇠를 열 수 있는 키카드를 만드는 것이 여러분의 과제다.

• $2 \le N \le 150$
• $0 \le A[i] \le 1$ (각 $i$에 대해 $0 \le i < N$)
• $0 \le S[i][0] < N$이고 $0 \le S[i][1] < N$ (각 $i$에 대해 $0 \le i < N$)
• $1 \le M \le 50\,000$
• $0 \le B[j] \le 1$ (각 $j$에 대해 $0 \le j < M$)
• $0 \le T[j][0] < M$이고 $0 \le T[j][1] < M$ (각 $j$에 대해 $0 \le j < M$)
• $K = N$