Sum of Subexpression Evaluations

You are given a boolean expression of length (2N-1) in the form [ a_1 ; op_2 ; a_2 ; op_3 ; a_3 ; \dots ; op_N ; a_N ] where each digit (a_i) is either 0 or 1 and each operator (op_i) (for (2 \le i \le N)) is one of &, | or ^. These operators represent the bitwise operations AND, OR and XOR respectively. Note that there is no operator precedence – the operations are evaluated strictly from left to right.

A subexpression is defined as any contiguous segment of the expression that starts and ends with a digit (a single digit is also considered a subexpression). The value of a subexpression is computed by evaluating the expression from left to right. For example, for the subexpression [ a_i ; op_{i+1} ; a_{i+1} ; \dots ; op_j ; a_j ] the value is computed as [ v = a_i, \quad v = ((v ; op_{i+1} ; a_{i+1}) ; op_{i+2} ; a_{i+2}) ; \dots ; op_j ; a_j. ]

Initially you are given the expression. Then you have to perform (Q) modifications. Each modification is given by three tokens:

• An integer (pos) ((1 \le pos \le N)).
• A new operator string, denoted by nop. (When (pos=1) the operator is ignored.)
• A new digit (nx) (which is 0 or 1).

For a modification with (pos \ge 2), you should change the operator (op_{pos}) to the given nop and the digit (a_{pos}) to (nx). When (pos=1), only update (a_1) to (nx) (the operator is ignored).

After each modification, output the sum of the values of all subexpressions of the current expression.

Note that since every subexpression evaluates to either 0 or 1, you are effectively being asked to count how many subexpressions evaluate to 1.

All formulas in this statement are given in (\LaTeX) format.

inputFormat

The first line contains two integers (N) and (Q), representing the number of digits in the expression and the number of modifications respectively.
The second line contains (N) space‐separated integers (each 0 or 1) representing (a_1, a_2, \dots, a_N).
The third line contains (N-1) characters (each one of &, | or ^) without spaces, representing (op_2, op_3, \dots, op_N).
Each of the next (Q) lines contains a modification in the format:

[ pos ; nop ; nx ]

Here, when (pos=1) the given operator is ignored.

outputFormat

After each modification, output a single line containing one integer – the sum of values of all subexpressions of the current expression.

sample

3 2
1 0 1
&^
1 x 0
2| 1

3
3