Problem D
Halting After All

A Turing machine is a simple mathematical model for a computer. It consists of a list of tuples of the form $<s,i,t,o,d>$, a memory tape with individual cells containing either $0$ or $1$, a state, and an input/output head. The memory tape can be modeled as an infinite array starting at index $0$. The execution of the machine proceeds in steps like this. At step $0$, the initial state is $0$. If at any given step the machine is in state $s$, the content of the cell of the memory tape at the index of the input/output head is input $i$, and the machine has tuple $<s,i,t,o,d>$, then the state of the machine becomes $t$, the content of the cell of the memory tape at the index of the head becomes $o$, and the head moves left (the index is decremented) if $d$ is $0$ or it moves right (the index is incremented) if $d$ is $1$.

For example, if the machine is in state $3$, the input/output head is $6$, the cell at index $6$ of the memory tape contains $0$, and the machine has the tuple $<3,0,8,1,1>$, then the machine moves to state $8$, writes $1$ in the cell at index $6$, and moves the head right to $7$. The head starts at index $0$ and can never move left of $0$ (if the head tries to move left of $0$, it should stay at $0$ instead). If a machine reaches the state $-1$, it halts.

The memory tape is assumed to contain all $0$s at step $0$, except for an arbitrary, but constant number of cells. This constant sequence of arbitrary $0$s and $1$s starting at index $0$ is known as the input. (Think of it as a binary string stored in an array with each character stored in a single cell). The famous halting problem asks whether an arbitrary Turing machine halts on a given input. This problem is known to be undecidable in the general case, thus unsolvable.

We consider here an exotic version of the halting problem: we ask whether an arbitrary Turing machine halts within a constant number of steps on all possible inputs (the set of all possible inputs is infinite). Can you achieve what seems impossible?

Input

The first line is $1 \leq L \leq 20$, the number of steps for which you need to check if the machine halts on all possible inputs. The second line is $1 \leq S \leq 100$, the number of states in the machine. On the following $2S$ lines, each contains a tuple of the form:

$s~ i~ t~ o~ d$

where:

• $s$ is the state in which the machine currently is,

• $i$ is the input character read by the machine,

• $t$ is the state in which the machine is after the execution of the current step,

• $o$ is the output of the machine on the tape, and

• $d$ is the direction in which the input/output head moves one cell after the current step.

Output

For each machine, print $1$ if the machine terminates in L steps on all input, or print $0$ if the machine does not halt in L steps for at least one input.

17
1
0 0 0 1 1
0 1 0 0 0

0

20
1
0 0 -1 0 0
0 1 -1 0 0

1