题目背景

小 G 觉得上一道数学题太愚蠢了，所以出了一道数据结构题作为作业。

题目描述

小 G 有一个长度为 $2N-1$ 的逻辑表达式，形如 $a_1 \space op_2\space a_2\space op_3\space a_3 \dots op_N\space a_N$，其中 $a_i \in \{ 0,1\}$，$op_i$ 为 &，| 或 ^。

& 表示与运算，| 表示或运算，^ 表示异或运算。运算符之间不分优先级。

定义一个表达式的子表达式为它的一个连续区间，满足区间左端点，右端点均为数字。特别地，单独一个数字也算在内。

现在小 G 想知道，这个表达式的所有子表达式计算结果的和是多少？

小 G 觉得这个问题太简单了，所以决定进行 $Q$ 次修改。每次修改给定 pos nop nx，表示将 $op_{pos}$ 改为 $nop$，$a_{pos}$ 改为 $nx$。特别地，当 $pos=1$ 时，$nop$ 可忽略。你需要在每次修改后，都输出这个表达式的所有子表达式计算结果的和。

输入格式

第一行包含两个正整数 $N$ 和 $Q$，表示变量的个数和询问的次数。

第二行包含长度为 $2N-1$ 的字符串 $S$，表示小 G 的逻辑表达式。

接下来 $Q$ 行，每行形式为 pos nop nx。

输出格式

包含 $Q$ 行，每行一个数字，表示答案。

4 4
1&1^0|0
4 ^ 1
4 | 0
1 | 0
2 & 0

7
7
3
0

10 10
1|1|1^1|0^0&0|0|1&1
6 ^ 1
9 & 1
7 ^ 1
1 ^ 1
1 | 0
7 | 1
6 & 1
2 ^ 1
8 | 1
2 & 1

32
16
24
24
23
43
40
40
43
42

提示

样例解释 #1

第一次操作后，逻辑表达式为 1&1^0^1，子表达式有 1、1、0、1、1&1、1^0、0^1、1&1^0、1^0^1、1&1^0^1，计算结果之和为 $1+1+0+1+1+1+1+1+0+0=7$。

数据范围

对于 $100\%$ 的数据，保证 $1 \le N,Q \le 10^6$。