Stack Machine Interpreter with Typed Int and String Values

You are building an interpreter for a simple stack machine. The machine has a single stack, and every value on the stack is one of exactly two primitive types:

• an integer (e.g., 7), or
• a string (e.g., "7").

The integer 7 and the string "7" are different values and must never be conflated. Your value representation must preserve this type distinction at all times.

The machine executes a sequence of parsed instructions, one at a time, against the same persistent stack. There are four instruction kinds:

1. PUSH v — push the value v onto the stack. The operand v is either an integer or a string, and its type is known at parse time.
2. POP — remove the top value from the stack and discard it.
3. POP_AND_PRINT — remove the top value from the stack and print it to standard output on its own line. An integer is printed in its usual decimal form; a string is printed as its raw characters (no surrounding quotes).
4. ADD — pop the top two values from the stack, combine them, and push the result back onto the stack:

• If both values are integers, push their integer sum.
• If at least one value is a string, convert any integer operand to its decimal string representation and push the concatenation. The value that was deeper in the stack (pushed earlier) comes first in the concatenated result, followed by the value that was on top.

Implement a function operate(instruction) that applies one instruction to the machine's stack, and use it to process an entire program (a list of instructions in order). You may design the parsed-instruction representation however you like, but it must carry both the operation and, for PUSH, a typed operand that distinguishes integers from strings — including in languages where a single variable cannot naturally hold "int or string."

Input

A program given as a list of instructions, in execution order. In the textual form, one instruction appears per line:

• PUSH 7 pushes the integer 7 (operand written without quotes).
• PUSH "7" pushes the string 7 (operand written in double quotes).
• POP, POP_AND_PRINT, and ADD take no operand.

Output

The values printed by each POP_AND_PRINT, one per line, in execution order. If the program prints nothing, output nothing.

Example

Input:

PUSH 7
PUSH 7
ADD
POP_AND_PRINT
PUSH 7
PUSH "7"
ADD
POP_AND_PRINT
PUSH "ab"
PUSH "cd"
ADD
POP_AND_PRINT

Output:

14
77
abcd

Explanation:

• 7 + 7 is int + int, so integer addition gives 14.
• 7 + "7" involves a string, so the integer 7 becomes the string 7 and concatenation gives the string 77 (not the integer 14).
• "ab" + "cd" concatenates to abcd; the earlier-pushed value (ab) comes first.

Constraints

• $1 \le$ number of instructions $\le 10^5$.
• Integer operands and all intermediate integer sums fit in a signed 64-bit integer.
• String operands consist of printable ASCII characters, may be empty, and may contain digit characters (a string of digits is still a string).
• The total length of all string values ever created during execution does not exceed $10^6$ characters.
• The program is guaranteed to be valid: POP and POP_AND_PRINT are only issued when the stack is non-empty, and ADD is only issued when the stack holds at least two values.