Expressions

Part of the training in arithmetic classes at Tomorrow Programming School is evaluating a given arithmetic expression quickly, in your head only. The expressions contain only positive integers, no brackets, and only three operations: addition, subtraction, and multiplication. The result is therefore guaranteed to be an integer. At introductory stages, a student only has to find the parity of the result: is it odd or even?

Unfortunately, the professor who writes the expressions on the blackboard is quite absentminded. He often rewrites various numbers in an expression, sometimes several more times while the students are already calculating. A rewrite usually changes the value of the whole expression, so the students have to start over.

The students decided to write a program to help them. The input is the original expression and the sequence of subsequent value changes. For each change, the program calculates the value of the modified expression, reusing earlier work where possible instead of recalculating from scratch.

The first line contains two integers $N$ and $M$ ($1 \le N, M \le 10^5$), the number of integers in the expression and the number of subsequent value changes. The second line contains $N$ space-separated tokens. Each token is an integer $A_i$ ($1 \le A_i \le 10^9$) or one of +, -, * (addition, subtraction, multiplication). Each of the next $M$ lines contains two space-separated numbers $X$ ($1 \le X \le N$) and $Y$ ($1 \le Y \le 10^9$), meaning the $X$-th number in the expression is changed to $Y$.

The changes are applied in order. When a later change targets a different position, the earlier change stays in effect.

Output $M + 1$ lines. Line $i$ is even or odd, depending on whether the expression evaluates to an even or odd value after the first $i - 1$ changes. The first line gives the answer before any change. The expression follows standard operator precedence: multiplication is evaluated before addition and subtraction.