Practice Memoization and Lazy evaluation with the exercise "1D Spreadsheet"

3380

Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

Statement

Goal

You are given a 1-dimensional spreadsheet. You are to resolve the formulae and give the value of all its cells.

Each input cell's content is provided as an operation with two operands arg1 and arg2.

There are 4 types of operations:
VALUE arg1 arg2: The cell's value is arg1, (arg2 is not used and will be "_" to aid parsing).
ADD arg1 arg2: The cell's value is arg1 + arg2.
SUB arg1 arg2: The cell's value is arg1 - arg2.
MULT arg1 arg2: The cell's value is arg1 × arg2.

Arguments can be of two types:
• Reference $ref: If an argument starts with a dollar sign, it is a interpreted as a reference and its value is equal to the value of the cell by that number ref, 0-indexed.
For example, "$0" will have the value of the result of the first cell.
Note that a cell can reference a cell after itself!

• Value val: If an argument is a pure number, its value is val.
For example: "3" will have the value 3.

There won't be any cyclic references: a cell that reference itself or a cell that references it, directly or indirectly.

Input

Line 1: An integer N for the number of cells.
Next N lines: operation arg1 arg2

operation is one of { VALUE, ADD, SUB, MULT }
arg1 and arg2 are either a number ("-?[0-9]+"), a reference ("\$[0-9]+") or nothing "_".

Output

N lines: the value of each cell, one value per line, from cell 0 to cell N

Constraints

1 ≤ N ≤ 100
-10000 ≤ val ≤ 10000
$0 ≤ $ref ≤ $(N-1)
val ∈ ℤ
ref ∈ ℕ
There are no cyclic references.

Example

Input

2
VALUE 3 _
ADD $0 4

Output

3
7

Solve it

A higher resolution is required to access the IDE