Under construction

Still being built. Things may change

LVM

Time limit2sMemory limit512 MB

Summary
Simulate the stack machine program and print the value shown by the first DONE instruction.
Level

Easy3 of 10

Topics
Simulation, Stack
Solved
No attempts yet

Problem

You are building a virtual machine for a new programming language called Lombok. The Lombok Virtual Machine (LVM) runs assembler-like machine code on a stack and a single register.

The instructions behave as follows.

PUSH x pushes the given integer onto the stack. If the stack looks like this

and the machine executes PUSH -11, the stack afterwards looks like this:

STORE takes the topmost integer off the stack and stores it in the register. If the stack looks like this

the register holds some integer, and the machine executes STORE, the stack afterwards looks like this

and the register holds the integer 3.

LOAD copies the content of the register and pushes it onto the stack. If the register holds the integer 6, the stack looks like this

and the machine executes LOAD, the stack afterwards looks like this

and the register still holds the integer 6.

PLUS takes the two topmost integers off the stack, adds them, and pushes the result back onto the stack. If the stack looks like this

and the machine executes PLUS, the stack afterwards looks like this:

TIMES takes the two topmost integers off the stack, multiplies them, and pushes the result back onto the stack. If the stack looks like this

and the machine executes TIMES, the stack afterwards looks like this:

IFZERO n removes the topmost integer from the stack and checks whether it equals 0. If it does, execution jumps to instruction nn, counting from 0. If it does not, the machine continues with the next instruction.

DONE prints the integer on top of the stack and ends the program, no matter how many instructions follow it.

Execution starts at the first instruction. The stack starts out empty and the register starts out holding 0.

Input

The first line contains an integer nn between 2 and 1000, the number of instructions in the program. Each of the next nn lines contains one instruction. An argument is separated from its instruction by a single space.

The given program is correct. It never loops forever, and it never removes an integer from an empty stack. The stack never holds more than 100 integers. The argument of PUSH is an integer between -10000 and 10000, and the argument of IFZERO is an integer between 0 and 1000.

Output

Print a single integer: the value printed by the first DONE instruction that execution reaches.

Examples1

  1. Example 1

    Input
    14
PUSH 5
STORE
LOAD
LOAD
PUSH -1
PLUS
STORE
LOAD
IFZERO 13
LOAD
TIMES
PUSH 0
IFZERO 3
DONE
    Expected output
    120