[JRKSJ R3] 琴琴的树

琴琴有一棵二叉树，满足： * 该树有无穷多个结点。 * 每个结点都有编号和权值。初始所有结点的权值为 $0$。 * 树根的编号为 $1$。 * 若一个结点的编号为 $i$，则该结点的左右儿子的编号分别是 $2i,2i+1$。 琴琴要对树进行共 $m$ 次操作，每次操作是二者之一： 1. 将编号为 $x$ 的结点为根的子树中的每个结点的权值都加 $v$。 2. 求树上编号为 $x$ 的结点到编号为 $y$ 的结点的路径上每个结点的权值和。答案对 $2^{32}$ 取模。 不过琴琴不会直接给出 $x,y$。她再给出一个长度为 $n$ 的 $01$ 序列 $a$，每次给出 $x$ 或 $y$ 时给出一个区间 $[l_x,r_x]$ 或 $[l_y,r_y]$，这个数就是将这个区间视作二进制数的值。

第一行两个整数 $n,m$。\ 第二行一个长度为 $n$ 的字符串表示 $a$。保证字符串中只包含 `0` 和 `1`。\ 下面 $m$ 行，每行一个操作编号，然后是操作。操作的格式为： 1. $\ l_x\ r_x\ v$ 2. $\ l_x\ r_x\ l_y\ r_y$

对于每个操作 $2$，每行一个整数表示答案。

5 5
01010
1 4 5 5
2 1 3 2 5
1 2 3 3
2 1 5 1 2
2 3 4 4 5

15
24
8

### 样例解释 该树的前四层如图所示：  第一个操作：将以 $2$ 为根的子树中的结点权值加上 $5$。\ 第二个操作：求 $2\rightarrow 10$ 的路径上的点的权值和。\ 第三个操作：将以 $2$ 为根的子树中的结点权值加上 $3$。\ 第四个操作：求 $10\rightarrow 1$ 的路径上的点的权值和。\ 第五个操作：求 $1\rightarrow 2$ 的路径上的点的权值和。 ### 数据规模与约定 **本题采用捆绑测试。** | $\text{Subtask}$ | $n\le$ | $m\le $ | 分值 | | :----------: | :----------: | :----------: | :----------: | | $1$ | $10$ | $10^3$ | $5$ | | $2$ | $20$ | $10^5$ | $5$ | | $3$ | $10^4$ | $10^4$ | $20$ | | $4$ | $4\times 10^5$ | $4\times 10^5$ | $70$ | 对于 $100\%$ 的数据，$1\le n,m\le 4\times 10^5$，$1\le v \le 10^9$，$1\le l_x\le r_x\le n$，$1\le l_y\le r_y\le n$，保证 $x,y\ne 0$。