Just because UofT now teaches Java in the first year, it doesn't mean you can forget about Turing. Alan Turing pretty much defined computers by defining a computing device that has come to bear his name. Your task is to write a (simplified) Turing machine simulator.

A Turing machine is a state machine that reads and writes symbols on
an external memory called a *tape*, using a device called a
*head*.
In this question, those symbols will be a subset of the decimal digits
0 through 9, with
digit 9 representing a blank.

The tape is initialized to some non-empty string of digits, interpreted as the input to the machine.

There are *s*+2 states in the machine. The
*s*
active states are numbered 0 through *s*-1. State -1 is the accepting
state; state -2 is the rejecting state.

The ``program'' of the machine is stored in a table of triples indexed
by an active state number and a symbol.
If the triple stored for state *q* and symbol *d* is (*d*',*m*,*q*'),
then whenever the machine is in state *q* and sees symbol *d* under
its head, then the head overwrites *d* with *d*', moves its head
*m* positions right
(*m* is either 1 or -1; -1 means move left one symbol), and enters
state *q*'.

The machine starts in state 0 with its head positioned over the leftmost
symbol of the tape. It then repeatedly takes
steps according to the above rule.
If the machine ever enters state -1, it *accepts* the input and stops.
If it ever enters state -2, it *rejects* the input and stops.
If it ever tries to move to the left of where its head started, it
*rejects*
the input and stops.
If it ever tries to move to the right of the digit string currently
on the tape, it interprets
the new (blank) cell as being filled with symbol 9, and continues.

Input: The machine and its input are described using numbers and
digit strings, separated by whitespace (spaces, tabs, and newlines).
The first item is a digit symbol *d*; the machine uses symbols
0 through *d*, and 9.
The second item is *s*, is the number of active states.

The next items encode the state transition table. Triples are provided
for all possible state transitions, and are presented
in order: all triples indexed by state 0 come first, then all
those indexed
by state 1, up until all those indexed by *s*; within each such ``row'',
the triples are ordered with the triple indexed by symbol 0 first,
up until the triple indexed by symbol *d*, and finally the triple
indexed by 9 (the ``blank'').
Each triple is
a digit symbol *d*', and
then
a move number -1 or 1, and
finally a state number *q*'.
The input will always be valid.

Finally, a decimal string of up to 100 digits is given, and it is interpreted as the string of initial values of the tape cells.

The Turing machine programs presented will never use more than 1000 tape cells, and will always eventually stop by either accepting or rejecting.

Output:
Given a machine description and an input, simulate the machine until it
stops.
If it has accepted, print the string `accept` followed by
a single space, followed by the contents of the tape and a single newline.
If it has rejected, print the string `reject` followed by
a single space, followed by the contents of the tape and a single newline.
By ``the contents of the tape'',
we mean the contents of any squares
that had a specified value (including 9) at input time, or over which
the machine's read/write head passed during execution.

Description of sample machine:
The machine in the samples below
treats its input as a binary number *n*. If and *n* is
divisible by 4, then the machine leaves a binary representation of *n*/4
on the tape (with some trailing 9's representing blanks),
and accepts. Otherwise, the
machine rejects.

Sample input:

1 4 0 1 0 1 1 0 9 -1 1 9 -1 2 9 -1 3 9 -1 -2 9 -1 -1 9 -1 -2 9 -1 -2 9 -1 -2 9 -1 -2 9 -1 -2 010100Corresponding output:

accept 0101999Sample input (same machine, different input):

1 4 0 1 0 1 1 0 9 -1 1 9 -1 2 9 -1 3 9 -1 -2 9 -1 -1 9 -1 -2 9 -1 -2 9 -1 -2 9 -1 -2 9 -1 -2 110101Corresponding output:

reject 1101999

Thu Sep 18 16:32:16 EDT 1997