Your friend has hired you to work at their startup, which is in the business of bespoke calculator hardware. You are tasked with making the firmware for one of the calculators, but its button layout is unlike any you've seen before. The calculator has a record of numbers, and performs operations on it until there are no instructions and one output in the record remaining. The layout and behaviour is outlined below.

• The is a typical 0-9 keypad, which adds that number to the record.
• There is a '+' key, which removes the last two numbers from the record and adds their sum.
• There is the 'B' key, which deletes the most recent number from the record.
• There is the 'C' key, which clears all numbers from the record.
• There is the 'T' key, which removes the number from the top of the record and adds a third of it, rounding down.
• There is the 'D' key, which removes the number from the top of the record and adds double it.

Input

The first line contains an integer ~n\ (1 \leq n \leq 1000)~ detailing the number of button inputs.

The next ~n~ lines each contain a single ASCII character.

Output

Output the number produced by these operations on a single line. In an error state, please just output "INVALID" instead.

The possible error states are:

• A character inputted is not one of the ones defined above.
• An operation is called but the record does not have enough numbers to perform it. B, T, D require one value, + requires 2 values.
• The record has more than 1 number in it on program conclusion.

The tests are formulated such that a 32-bit integer will be able to contain every intermediary and output, and you may notice that negative numbers cannot be generated using these operations.

Example

Input 1

7
2
9
+
3
B
D
T

Output 1

7

The process goes like this: [2] -> [2,9] -> [11] -> [11, 3] -> [11] -> [22] -> [7]

Input 2

10
1
2
+
3
D
C
5
2
D
+

Output 2

9

[1] -> [1,2] -> [3] -> [3,3] -> [3,6] -> [] -> [5] -> [5, 2] -> [5, 4] -> [9]

Input 3

4
1
2
+
3

Output 3

INVALID

[1] -> [1,2] -> [3] -> [3,3]

The record must have only 1 number in it at the end of execution.

Input 4

5
2
3
+
+
E

Output 4

INVALID

[2] -> [2,3] -> [5] -> ?

The + command requires 2 operands from the record, so the second one triggers INVALID output. Also, the command E is not defined, so this would also trigger an INVALID output.