Description

To simplify the problem, the program contains only loops and sequential structures. The program structure is defined as follows:

$\texttt{begin <statement> end}$

The structure of a statement block is recursively defined as follows:

$\texttt{loop x <statement> end}$

or $\texttt{op <statement>}$

or $\texttt{break <statement>}$

or $\texttt{continue <statement>}$

A statement block can be empty.

Notes:

1. A program starts with $\texttt{begin}$ and ends with the corresponding $\texttt{end}$.

2. $\texttt{loop x <statement> end}$ means the statements inside are executed repeatedly $x$ times.

3. $\texttt{op x}$ means performing $x$ unit operations.

4. In the above two points, $x$ can be a positive integer or $n$.

5. The $\texttt{break}$ statement exits the current loop level, and the $\texttt{continue}$ statement skips the remaining statements in the current loop level and directly enters the next iteration. If it ($\texttt{break}$ or $\texttt{continue}$) is not inside any loop, please ignore them.

You need to write a program to compute the time complexity of the program described above, and output it in polynomial form.

Note that this polynomial is a polynomial in $n$, and the constant term and coefficients cannot be omitted.

The testdata guarantees that the time complexity of the program can be determined.

Input Format

The input contains a complete program.
Between every two statements, there is at least one space or newline character.

Output Format

Output the computed time complexity polynomial in descending order of degree.

begin loop n loop 3 loop n
op 20
end end end
loop n op 3 break end
loop n loop n
op 1
break
end end
end

60n^2+n+3

begin
op n
loop 3
op n
break
end
loop n
loop n
op 1
continue
op n
end
end
end 

n^2+2n

Hint

The loop nesting depth is at most $20$ levels.

It is guaranteed that the coefficient of each term in the final time complexity polynomial does not exceed ${10}^9$.

Translated by ChatGPT 5