This is a submission-based problem.

The Flea Kingdom, as a developing country, has productivity significantly lower than that of the developed Flea-Late Kingdom. Therefore, developing productivity has always been the top priority for the Flea Kingdom.

Recently, while inspecting Factory X in the capital of the Flea Kingdom, the Flea King discovered that the machines there were inefficient and highly polluting, causing the capital to be covered in smog almost every day.

Factory X is used to inspect the quality of products shipped from various locations. Each workshop in Factory X contains several nodes. Each node has a machine that processes a product and then sends it to the next node.

Recalling his experience building computers a few months ago, the Flea King had a brilliant idea: use efficient and clean biological resources! Thus, the machines at each node were replaced with fleas.

Specifically:

• For each workshop in Factory X, we can number all nodes starting from $1$.
• For each product, there is an identifier string consisting only of visible characters (ASCII values in the range $[32, 126]$).

Initially, a product is sent to node $1$. These nodes then inspect the product's identifier string and eventually Accept or Reject the product.

• For different workshops, the set of identifier strings that must be accepted is different.
• A flea at a node has two attributes: trans and next. trans is an integer array of size $128$, and next is an integer.

When a product is sent to this node, the first character of the product's identifier string is removed. Let its ASCII value be $x$. The product will be sent to the node numbered trans[x] in the next second. If the identifier string is already empty, the product will be sent to the node numbered next in the next second.

The Cricket King expressed his full support and sent some crickets to increase the processing capacity of Factory X. That is, a flea at a node can be replaced by a cricket.

• Each cricket has two integer attributes: x and next. The range of x is $[0, 127]$.
• When a product is sent to this cricket node, a character with ASCII value x is appended to the end of the product's identifier string, and the product is then sent to the node numbered next in the next second.

Additionally, for the trans or next of any flea, and the next of any cricket, the value can be $0$ or $-1$, where $0$ means the product is accepted in the next second, and $-1$ means the product is rejected in the next second.

Due to resource limitations in the Flea Kingdom, a workshop can have at most $300$ nodes. When processing a product, at most $10^6$ seconds can be spent.

The Flea King found that he did not have the ability to manage so many fleas and crickets, so he turned to you, a participant in the Tsinghua training camp. Please determine the number of nodes $n$ to be used for each workshop in Factory X, as well as the attributes of the flea or cricket used at each node. Each workshop is treated as a task, with requirements as follows:

Task 1 (5 points)

Accept all products whose identifier strings are 01-strings ending in 1. For example, "111" is a 01-string ending in 1, while "110" and "233" are not. It is guaranteed that for each product, the length $L$ of the identifier string satisfies $1 \le L \le 100$.

Task 2 (13 points)

Accept all products whose identifier strings contain the substring

aaaaaaaaaaaabaaaaaabaaaaaaaaaaaaaabaaabaaabaaaaaaaaaabaaaaaaaaabaabaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaorz

This substring is also provided in the file task2_string.txt in the problem directory. It is guaranteed that for each product, the length $L$ of the identifier string satisfies $1 \le L \le 500000$.

Task 3 (9 points)

Accept all products whose identifier strings are matched parenthesis strings. A matched parenthesis string can be defined as follows:

• The empty string is a matched parenthesis string.
• If $S$ is a matched parenthesis string, then $(S)$ is a matched parenthesis string.
• If $X$ and $Y$ are both matched parenthesis strings, then $XY$ is a matched parenthesis string.

For example, "(())()" is a matched parenthesis string, while "(()" is not. An equivalent context-free grammar is:

S -> SS | (S) | ε

It is guaranteed that for each product, the length $L$ of the identifier string satisfies $1 \le L \le 100$.

Task 4 (12 points)

Accept all products whose identifier strings are matched parenthesis strings. The definition of a matched parenthesis string is the same as in Task 3. It is guaranteed that for each product, the length $L$ of the identifier string satisfies $1 \le L \le 900000$.

Task 5 (6 points)

Accept all products whose identifier strings are 01-strings that represent a multiple of 3 when read as a binary number from left to right. For example, $(10010)_2 = (18)_{10}$, so a product with the identifier string "10010" is acceptable. It is guaranteed that for each product, the length $L$ of the identifier string satisfies $1 \le L \le 100$.

Task 6 (15 points)

Accept all products whose identifier strings are fib-strings. A fib-string can be defined as follows:

• Let f[1] = "a", f[2] = "b".
• For $i > 2$, we define f[i] = f[i - 1] + f[i - 2], where + denotes string concatenation.
• For example, f[3] = "ba", f[4] = "bab".
• A string $s$ is a fib-string if and only if there exists a positive integer $i$ such that $s$ equals f[i].

For example, "bab" is a fib-string, while "baa" is not. It is guaranteed that for each product, the length $L$ of the identifier string satisfies $1 \le L \le 400$.

Task 7 (8 points)

Accept all products whose identifier strings are fib-strings. The definition of a fib-string is the same as in Task 6. It is guaranteed that for each product, the length $L$ of the identifier string satisfies $1 \le L \le 200000$.

Task 8 (14 points)

Accept all products whose identifier strings are expressions. An expression can be defined as follows:

• First, introduce another definition: term.
• Any term is an expression.
• "0" and "1" are terms.
• If $X$ is an expression, then $(X)$ is a term.
• If $X$ and $Y$ are terms, then $X*Y$ is a term.
• If $X$ and $Y$ are expressions, then $X+Y$ is an expression.

For example, "(1+0)*1+0+(1)" is an expression, while "(1+1" is not. An equivalent context-free grammar is:

S -> S + T | T
T -> T * F | F
F -> 0 | 1 | (S)

It is guaranteed that for each product, the length $L$ of the identifier string satisfies $1 \le L \le 1000$.

Task 9 (7 points)

Accept all products whose identifier strings are expressions. The definition of an expression is the same as in Task 8. It is guaranteed that for each product, the length $L$ of the identifier string satisfies $1 \le L \le 100000$.

Task 10 (11 points)

Accept all products whose identifier strings are Flea Language strings.

• Flea Language is a language consisting only of statements and control structures.
• For convenience, Flea Language consists of only three characters: 'i', 'e', and 'a'.
• 'a' represents a statement, 'i' represents if, and 'e' represents else.
• A Flea Language string can be a statement or a control structure.
• A statement is "a", and a control structure is "iAeB" or "iA", where A can be a statement or a control structure, and B can be a statement or a control structure.
• For an 'e', it always matches the nearest preceding 'i'.

For example, "iiaea" is a Flea Language string because its suffix "iaea" as a whole control structure forms an "iA" type control structure with the first "i". "iaeaea" is not a Flea Language string because its last "ea" cannot find a matching "i". "iiaeaea" is a Flea Language string, where the first "ea" matches the second "i", and the second "ea" matches the first "i".

An equivalent context-free grammar is:

S -> iSeS | iS | a
where e matches the nearest i, i.e., iSeS has higher priority than iS.

It is guaranteed that for each product, the length $L$ of the identifier string satisfies $1 \le L \le 100$.

Input

All input data factory1.in ~ factory10.in correspond to the 10 tasks respectively. Each input file contains only one integer, representing the task number to be solved.

Output

The output files are 1.out ~ 10.out, corresponding to the respective input files. For each input, you need to output the nodes you used. Specifically, the first line outputs an integer $n$, representing that you used nodes numbered $1 \sim n$. The next $n$ lines describe each node in increasing order of their numbers. First, output an integer representing the type of the node, where $1$ is a flea and $2$ is a cricket. For a flea node, output $128$ integers representing trans[0] ~ trans[127], followed by an integer next. For a cricket node, output two integers x and next. It is required that trans[i] and next are in the range $[-1, n]$, where the meanings of $-1$ and $0$ are as described in the problem. It is required that x is in the range $[0, 127]$. Adjacent integers on the same line are separated by a space.

At the end of the output file, you may add any content; this will not affect your score. We suggest you write some meaningful content here (such as the construction method for this task) so that we can perform statistical analysis after the exam.

Scoring

This problem has no partial points.

We provide 10 scoring files factory1.ans ~ factory10.ans, corresponding to each task.

In each scoring file, the first line is an integer $m$, representing $m$ test cases. The next $2m$ lines represent the test cases, where every two lines consist of a string representing the identifier string of the test case, and a string "Accept" or "Reject" representing the answer for that test case.

In this problem, we score each task individually. The points for each task are as described in the problem.

If your output format is invalid or the parameters do not meet the problem requirements, you will receive 0 points.

Otherwise, the scoring follows these rules:

• First, the grader will read the test data for the task from the corresponding scoring file and substitute each test case into your output.
• If, when substituting a test case, the time taken to process the product exceeds $10^6$ seconds, you will receive 0 points.
• If, when substituting a test case, your output does not match the corresponding answer, you will receive 0 points.
• Otherwise, you will receive full points for the task.

How to test your output

In the terminal, first switch to the directory of the problem: (Windows users please use cmd)

cd factory

We provide a tool called checker to test whether your output file is acceptable. To use this tool, first compile checker.cpp. Assuming the compiled file is named checker, run the following in the terminal:

./checker <task_id>

where task_id is the task number, for example:

./checker 3

This will test whether 3.out is acceptable. (Windows users please use checker 3) After you call this program, the checker will provide the test results based on your output file. Additionally, you can run checker without parameters to test all output files for this problem.

We also provide some other small tools, such as tools for running/debugging your output files. Detailed instructions can be found in readme.txt in the problem directory.