Background

CTSC1998 D1T3.

When we do programming, the issue we care about most is the time complexity of an algorithm. However, analyzing the complexity of a program is very difficult, and it becomes even harder when the program is not well written.

So, the SERKOI group, which specializes in studying algorithms, decided to develop software to analyze the time complexity of a program. Since this is a brand-new field, the SERKOI group decided to start with simple cases first.

Problem 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