cho.sh

Hal's Calculator

Time limit1sMemory limit128 MB

Problem

Hal has a symbolic calculator whose memory is a list holding at most 100 elements. Each element stores an arithmetic expression built only from the symbols A, B, #, $, (, ). The element at the front of the list is the first (top) element, the next is the second, and so on.

The calculator starts with a list of exactly two elements: the first element holds A and the second holds B.

The calculator understands these commands:

  • HASH — if the first element holds expression s and the second holds expression t, remove both and create a new first element holding (t#s).
  • DOLLAR — if the first element holds s and the second holds t, remove both and create a new first element holding (t$s).
  • SWAP — exchange the first and second elements.
  • DROP — remove the first element.
  • DUP — create a new first element that is a copy of the current first element.
  • ROT — rotate the first four elements so that the first becomes the second, the second becomes the third, the third becomes the fourth, and the fourth becomes the first.

For example, if the list is A, B (with A on top), HASH replaces the top two elements with the single element (B#A).

A command fails (and the program is invalid) when there are not enough elements to run it, or when running it would make the list longer than 100 elements:

  • DUP and DROP need at least one element.
  • HASH, DOLLAR, and SWAP need at least two elements.
  • ROT needs at least four elements.
  • Only DUP can grow the list; it fails if the list already holds 100 elements (adding a 101st element is not allowed).

Given a program (a sequence of commands), run it on Hal's calculator starting from the initial list and report the resulting list.

Input

The first line contains an integer N (0 ≤ N ≤ 10000), the number of commands. Each of the next N lines contains one command, which is one of HASH, DOLLAR, SWAP, DROP, DUP, ROT.

Output

If every command runs successfully, print the final list from the first (top) element to the last, one expression per line. If any command fails, print a single line containing ERROR.