Transformation of an expression tree using enum and…

Given an arithmetic expression represented as a binary tree. Each tree node is either a number (leaf) or an operation (addition, subtraction, multiplication, division) with two children. It is necessary to implement a function that takes such a tree and returns a new tree simplified according to the following rules: if a node is an operation and both its children are numbers, compute the result and replace the node with a number; if one of the children is the number 0 and the operation is multiplication, replace the node with 0; if one of the children is the number 0 and the operation is addition, replace the node with the other child; if the operation is division and the divisor is the number 1, replace the node with the dividend; if the operation is subtraction and both children are equal, replace the node with the number 0. Apply recursively as long as possible. It is guaranteed that all operations are integer, division is integer division with rounding down. Input: first, the number n — the number of nodes. Then n lines, each in the format: node type ("num" or "op"), for "num" — the value (integer), for "op" — the operation symbol ('+', '-', '*', '/') and two integers — the indices of the left and right children (0-indexed). The root always has index 0. Output: for each node after simplification, output its type and value/operation in the same format (node order — as in the original tree, even if the node became a number, keep its index). If the node became a number, output "num value"; if it remained an operation, output "op symbol left_index right_index" (child indices — from the simplified tree).

Input Format

Integer n (1 ≤ n ≤ 1000). Then n lines: for a number: "num x"; for an operation: "op op_symbol left right".

Output Format

n lines: for each node in the original order: "num value" or "op symbol left right".

Examples

Example 1

INPUT

3
num 5
num 3
op + 0 1

OUTPUT

num 5
num 3
op + 0 1

Example 2

INPUT

cat dog elephant bird

OUTPUT

cat dog bird elephant

Example 3

INPUT

5
num 0
num 7
op * 0 1
num 2
op + 2 3

OUTPUT

num 0
num 7
op * 0 1
num 2
op + 2 3

Example 4

INPUT

a ab abc abcd

OUTPUT

a ab abc abcd