P11685 [Algo Beat Contest 001 G] Great DS Homework

| Problem | Score | Idea | Std | Data | Check | Solution | | :---------------------------------: | :---: | :---------------------------------------------------: | :----------------------------------------------------------: | :---------------------------------------------: | :----------------------------------------------------------: | :----------------------------------------------------------: | | $\text{G - Great DS Homework}$ | $600$ | [orchardist](https://www.luogu.com.cn/user/347582) | [orchardist](https://www.luogu.com.cn/user/347582) | [joe_zxq](https://www.luogu.com.cn/user/623577) | [remmymilkyway](https://www.luogu.com.cn/user/551981) & [joe_zxq](https://www.luogu.com.cn/user/623577) | [Link](https://www.luogu.com.cn/article/xkcrwcoz) by [orchardist](https://www.luogu.com.cn/user/347582) | 小 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$ 可忽略。你需要在每次修改后，都输出这个表达式的所有子表达式计算结果的和。

无

无

#### 样例解释 #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$。