Time Complexity Polynomial Evaluation

Given a simple program that contains only loops and sequential structures, your task is to compute its time complexity and output it as a polynomial in (n).

The program follows the grammar below (all formulas are in (\LaTeX) format):

[ \texttt{begin ; ; end} ]

A block of statements is defined recursively as follows:

[ \texttt{loop; x; ; end} ]

or

[ \texttt{op; x} ]

or

[ \texttt{break} ]

or

[ \texttt{continue} ]

A block may be empty. The following notes explain the semantics:

1. A program always starts with (\texttt{begin}) and ends with the matching (\texttt{end}).
2. (\texttt{loop x end}) means the body is executed (x) times. Here, (x) can be either a positive integer or the symbol (n).
3. (\texttt{op x}) means executing (x) unit operations; (x) can be a positive integer or (n).
4. The (\texttt{break}) statement (if it is inside a loop) causes an immediate exit of the current loop (ignoring the remaining statements in that iteration). Similarly, (\texttt{continue}) (if inside a loop) skips the remaining statements in the current iteration and moves directly to the next iteration. If either (\texttt{break}) or (\texttt{continue}) appears outside any loop, they are ignored.

Your task is to compute the overall cost (i.e. the number of unit operations executed) of the given program and output the result as a polynomial in (n). The resulting polynomial must include the constant term as well as the coefficients, even if they are 0. For example, if the cost is (n^2) then it must be printed in the form:

0 + 0n + 1n^2

Note that the program is structured in a recursive manner using only the above constructs.

It is guaranteed that the provided program has a computable time complexity.

inputFormat

The input consists of multiple tokens forming a program. The tokens are separated by whitespace. The program always starts with the token begin and ends with the corresponding end. Tokens can be:

• begin • end • loop • op • break • continue • a positive integer (for constant counts) • n (representing the variable)

You may assume the input is correct and follows the described grammar.

outputFormat

Output the time complexity as a polynomial in (n). The polynomial should list all terms from the constant (degree 0) term up to the highest degree, formatted as shown in the example. Each term should display its coefficient explicitly. For instance, if the computed polynomial is (n^2), then the output should be formatted as:

0 + 0n + 1n^2

sample

begin
  op 5
end

5