Problem E
Odwrotna Notacja Polska

When writing an arithmetic expression, we usually use infix notation, where operators appear between the operands they operate on. However, this can lead to ambiguous expressions. For example:

This could be interpreted as $5+(7 * 3)$ or as $(5+7) * 3$. Most programming languages use precedence rules to determine the order of operations, and also allow using parentheses to force a specific order of evaluation.

There are, however, notations where the order of operations is unambiguous. One such notation is Reverse Polish Notation, or postfix notation, where operators appear after the operands. So, $2+2$ would be written as follows:

2 2 +

And $5+(7 * 3)$ would be written like this:

7 3 * 5 +

Without yet going into the details of how to evaluate these expressions, we can intuitively read this expression like this:

• 7 3 * evaluates to 21.

• The expression thus becomes 21 5 +.

• 21 5 + evaluates to 26.

Similarly, $(5+7) * 3$ would become this:

5 7 + 3 *

In this problem, we are going to concern ourselves with a very limited subset of this notation. Even so, our expressions will operate on integers and booleans, and we will support the following operators:

• Addition (+): Takes two integers and produces the sum of both integers.

• Multiplication (*): Takes two integers and produces the product of both integers.

• Equality (==): Takes two integers and produces a boolean value (true if the integers are equal, false otherwise)

• Logical AND (and): Takes two boolean values and returns true if both of them are true, and false otherwise.

• Logical OR (or): Takes two boolean values and returns true if one or both of them is true, and false otherwise.

An expression is composed of one or more tokens, which can be either operators (as described above), integers, or booleans. Evaluating an expression requires a stack data structure. The stack is initially empty, and we will process each token in the expression one by one, left to right, applying the following rules:

• If the token is an integer or a boolean (true or false), push it into the stack.

• If the token is an operator:

  • Check if the stack has at least two values. If not, this is a SYNTAX ERROR.

  • Pop two values from the stack. These will be the operands to the operator.

  • If the operands don’t have the same type (i.e., if one is an integer and the other is a boolean), this is a TYPE ERROR.

  • If the operator is addition, multiplication, or equality, but the operands are booleans, this is a TYPE ERROR.

  • If the operator is logical OR or logical AND, but the operands are integers, this is a TYPE ERROR.

  • At this point, we will know the operands are of the correct type. Apply the operator to the operands, and push the result into the stack.

We continue doing this until there are no tokens left in the expression (note that, if we encounter an error, we do not evaluate the expression further). If, after evaluating the expression, the stack is empty or contains more than one value, that is a SYNTAX ERROR. If there were no errors, the stack should have one (and only one) value in it. This value will be the result of evaluating the expression.

Input

The input contains a single line with the expression we want to evaluate. This will be a sequence of tokens, where each token is separated by a single space. The valid tokens are operators (+, *, ==, and, or), integers (for each integer $x$ you can assume that $0\leqslant x \leqslant 10\, 000$), and booleans (true or false). You can assume that there will be at least one token, but no more than 100 tokens.

Output

The output contains a single line with the result of evaluating the expression. If the expression produced no errors, this will be either an integer or a boolean. If the expression produced an error, the output will be either SYNTAX ERROR or TYPE ERROR.

1 2 + 3 1 + *

12

1 2 + 3 1 + * 12 ==

true

1 2 + 3 1 + * 12 == false and

false

1 2 + 3 1 + * 12 == 100 and

TYPE ERROR

1 2 3 *

SYNTAX ERROR