Background

CTSC1998 D1T3

When programming, one of the most critical concerns is the time complexity of algorithms. However, analyzing the complexity of a program is a challenging task, especially when the code style is not optimal.

Therefore, the SERKOI group, which specializes in algorithms, has decided to develop software for analyzing program time complexity. Since this is a new field, SERKOI has decided to start with simple cases for analysis.

Problem Description

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

$\texttt{begin <statement> end}$

A block of statements is recursively defined as follows:

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

or $\texttt{op <statement>}$

or $\texttt{break <statement>}$

or $\texttt{continue <statement>}$

A block of statements can be empty.

Notes:

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

2. $\texttt{loop x <statement> end}$ indicates that the statements inside are repeated $x$ times.

3. $\texttt{op x}$ indicates the execution of $x$ units of operation.

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

5. The $\texttt{break}$ statement is used to exit the current loop, and the $\texttt{continue}$ statement is used to skip the remaining statements of the current loop and proceed to the next iteration. If $\texttt{break}$ or $\texttt{continue}$ is not within any loop, ignore them.

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

Note that the polynomial is about $n$, and constant terms and coefficients must not be omitted.

The data guarantees that the time complexity of the program can be calculated.

Input Format

The input contains a complete program, with at least one space or newline separating each pair of statements.

Output Format

Output the calculated time complexity polynomial in descending order of powers.

Sample Input and Output

Sample Input #1

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

Sample Output #1

60n^2+n+3

Sample Input #2

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

Sample Output #2

n^2+2n

Notes

The nesting of loops does not exceed 20 layers.

The coefficients of each term in the final time complexity polynomial do not exceed $10^9$.

见题面 Input 部分

见题面 Output 部分