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.
Sample Input 1  Sample Output 1 

17 1 0 0 0 1 1 0 1 0 0 0 
0 
Sample Input 2  Sample Output 2 

20 1 0 0 1 0 0 0 1 1 0 0 
1 