题目描述

琴琴有一棵二叉树，满足：

• 该树有无穷多个结点。
• 每个结点都有编号和权值。初始所有结点的权值为 $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$ 的路径上的点的权值和。

数据规模与约定

本题采用捆绑测试。

对于 $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$。