K. SpongeBob to Shat El-Ghandoor
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

SpongeBob has failed his boating exam more times than anyone in Qa3 El-Hamoor can count. Patrick suggested he try Jordan instead, because he heard licenses are easy to get there. SpongeBob got excited and packed for Aqaba (LOL). Squidward, being the smart one, followed him to break the news: getting a license in Jordan is actually much harder, and there is a special test every boat rider must pass first. He handed SpongeBob a slip of paper with a formula on it. If SpongeBob can compute the string it describes, Squidward will let him keep heading to Shat El-Ghandoor. Help him out, because we all know he is going to need it.

A formula is a string composed of:

  • lowercase letters a–z, which expand to themselves.
  • repetition blocks of the form #[X], #{X}, or #(X), where # is a positive integer and $$$X$$$ is itself a formula (possibly empty).
  • the delete character !.

The expansion of a formula is defined as follows:

  • A letter expands to itself.
  • A sequence of items at the same level expands to the concatenation of each item's expansion, in order.
  • #[X] expands to the expansion of $$$X$$$ repeated # times, with no separator between repetitions.
  • #{X} expands to the expansion of $$$X$$$ repeated # times, with , (a comma followed by a space) placed between consecutive repetitions.
  • #(X) expands to the expansion of $$$X$$$ repeated # times, with ; (a semicolon followed by a space) placed after each repetition, including the last one.
  • ! deletes everything accumulated at its current bracket level so far. It is strictly scoped: a ! inside a bracket never affects anything outside that bracket. A ! with nothing to delete is a silent no-op.

Important: $$$X$$$ is expanded once and then repeated. So in 3[ab!cd], the inner ab!cd first becomes cd, then is repeated three times to give cdcdcd.

Input

A single line containing the formula $$$s$$$. It is guaranteed that:

  • $$$1 \le |s| \le 10^5$$$.
  • every repetition count is an integer in $$$[1, 10^6]$$$ with no leading zeros.
  • all brackets are balanced and every opener is preceded by its repetition count.
  • the maximum nesting depth of brackets is at most $$$100$$$.
  • the peak expansion length during evaluation is at most $$$10^6$$$ characters.
Output

Print the expansion of $$$s$$$ on a single line.

Examples
Input
2[2{2(a)}]
Output
a; a; , a; a; a; a; , a; a;
Input
5[ab!cd]
Output
cdcdcdcdcd
Input
2[3[a]!b]c!d
Output
d
Input
2{ab!cd}
Output
cd, cd
Input
1[1{1{ya}1{markeb}1{rayeh}1{alagabah}}]
Output
yamarkebrayehalagabah
Note

In Example 1, 2(a) expands to a; a; (two copies of a, each followed by ; ). Then 2{2(a)} joins two such strings with , between them, giving a; a; , a; a; . Finally 2[2{2(a)}] concatenates that with itself two times.

In Example 3, the outer 2[...] first builds 3[a] into its accumulator as aaa, then the inner ! wipes that, then b is added. The inner expansion is therefore b, repeated twice gives bb. At the root level the buffer becomes bb, then c makes it bbc, then the root ! wipes the whole root buffer, then d is appended. Output: d.