Large Number Calculation

Time limit2sMemory limit128 MB

Summary

Parse and evaluate an arithmetic expression with big integers up to 10^100, respecting operator precedence and floor division for negatives.

Level: Medium4 of 10
Topics: Math, String, Implementation
Solved: No attempts yet

Problem

You are given an expression made of integers and operators. The expression has no parentheses. Evaluate multiplication and division before addition and subtraction. Operators with the same precedence are evaluated from left to right.

The absolute value of each integer is at most 10^100. If a division result is not an integer, round it down. This also means a negative non-integer result is rounded toward the smaller integer.

Input

The first line contains the number of integers N (1 <= N <= 10).

The next 2N - 1 lines contain integers and operators (+, -, *, /) in alternating order. The first and last of these lines are integers, and each operator appears between two integers.

Output

Print the integer result after evaluating the expression.

Examples1

Example 1
Input
```
4
2
*
3
+
1
*
4
```
Expected output
```
10
```