P5698 [CTSC1998] Algorithm Complexity.

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.

To simplify the problem, the program contains only loops and sequential structures. The program structure is defined as follows: $\texttt{begin end}$ The structure of a statement block is **recursively defined** as follows: $\texttt{loop x end}$ or $\texttt{op }$ or $\texttt{break }$ or $\texttt{continue }$ 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 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.

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

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

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