H. Saki and Tree
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

This is an output-only problem.

Saki has invented a new programming language called Tree++. A program in Tree++ can be represented as a rooted binary tree where each non-leaf node has exactly two children, and has one of the following labels: "add", "sub", "mul", "quo", "rem", "pow". Here, a leaf node of a rooted tree is a node with no child.

A program in Tree++ accepts an integer $$$X$$$, and either outputs an integer, or produces an error according to the following rule.

  1. The program first writes the integer $$$X$$$ on each of the leaves.
  2. For each non-leaf node $$$u$$$ in decreasing order of depth, let $$$L$$$ and $$$R$$$ be the integer written on the left and right child.
    • If the label of $$$u$$$ is "add", $$$L+R$$$ is written on $$$u$$$.
    • If the label of $$$u$$$ is "sub", $$$L-R$$$ is written on $$$u$$$.
    • If the label of $$$u$$$ is "mul", $$$L\cdot R$$$ is written on $$$u$$$.
    • If the label of $$$u$$$ is "quo", it produces an error if $$$R \le 0$$$. Otherwise, the largest integer $$$q$$$ with $$$q\cdot R \le L$$$ is written on $$$u$$$.
    • If the label of $$$u$$$ is "rem", it produces an error if $$$R \le 0$$$. Otherwise, the unique integer $$$0 \le r \lt R$$$ which makes $$$L-r$$$ an integer multiple of $$$R$$$ is written on $$$u$$$.
    • If the label of $$$u$$$ is "pow", it produces an error if $$$R \lt 0$$$. Otherwise, $$$L^R$$$ is written on $$$u$$$. In particular, if $$$R=0$$$, $$$1$$$ is written on $$$u$$$ regardless of the value of $$$L$$$.
  3. If at any moment an integer with absolute value greater than $$$2^{100\,000}$$$ is written on a node, it produces an error.
  4. If an integer is successfully written on all nodes without an error, the program outputs the integer written on the root.

Satoru does not believe in the power of Tree++, so he challenged Saki to implement a short membership test for the 5 of his favourite numbers: $$$561$$$, $$$1105$$$, $$$1729$$$, $$$2465$$$, and $$$2821$$$. (Note that these are the 5 smallest Carmichael numbers, i.e. the composite numbers $$$x$$$ with $$$a^x=a \mod x$$$ for all integer $$$a$$$) More specifically,

  1. Saki must implement a program in Tree++ with the number of nodes equal or less than $$$150$$$.
  2. Satoru will run the program for the inputs $$$x=100, 101, \cdots, 3000$$$.
  3. For each $$$x$$$, the program must output $$$1$$$ if $$$x \in \lbrace 561, 1105, 1729, 2465, 2821\rbrace$$$, otherwise it must output $$$0$$$, without an error.

Write a program to help Saki implement the membership test.

Output

The output should be in the following format:

$$$N$$$$$$R$$$
$$$L_0$$$$$$L_1$$$$$$\cdots$$$$$$L_{N-1}$$$
$$$U_0$$$$$$V_0$$$
$$$\vdots$$$
$$$U_{N-2}$$$$$$V_{N-2}$$$

where

  • $$$N$$$ is the number of nodes, where nodes are numbered from $$$0$$$ to $$$N-1$$$,
  • $$$R$$$ is the root of the tree,
  • $$$L_i$$$ is the string "leaf" if the node $$$i$$$ is a leaf node, otherwise one of "add", "sub", "mul", "quo", "rem", "pow", for each integer $$$0 \le i \lt N$$$, and
  • $$$U_i$$$ and $$$V_i$$$ are the nodes that the $$$i$$$-th edge connects, where $$$U_i$$$ is the parent of $$$V_i$$$.

For an internal node, there are two edges connecting it to its children. The left child is the one connected to the edge appearing earlier in the output, while the right child is the one connected to the edge appearing later in the output.

The output should satisfy the following constraints:

  • All the numbers in the output, except for $$$L_i$$$, are integers.
  • $$$3 \le N \le 150$$$
  • The labelled rooted tree described by the output with must form a valid program in Tree++.
Example
Input
Output
11 0
add sub mul quo rem leaf leaf leaf leaf leaf leaf
0 1
0 2
1 3
1 4
2 5
2 6
3 7
3 8
4 9
4 10
Note
Please note that the sample output above does not implement the membership test for Satoru's favourite numbers, thus it will give Wrong Answer verdict upon submission. It is there only to present the output format.