Problem Description

Qinqin has a binary tree that satisfies:

• The tree has infinitely many nodes.
• Each node has an index and a weight. Initially, the weight of every node is $0$.
• The root node has index $1$.
• If a node has index $i$, then its left and right children have indices $2i$ and $2i+1$, respectively.

Qinqin will perform a total of $m$ operations on the tree. Each operation is one of the following:

1. Add $v$ to the weight of every node in the subtree rooted at the node with index $x$.
2. Query the sum of weights of all nodes on the path from the node with index $x$ to the node with index $y$ in the tree. The answer is taken modulo $2^{32}$.

However, Qinqin will not directly give $x$ and $y$. Instead, she gives a $01$ sequence $a$ of length $n$. Each time she needs to give $x$ or $y$, she provides an interval $[l_x,r_x]$ or $[l_y,r_y]$. The number is the value of this interval interpreted as a binary number.

Input Format

The first line contains two integers $n,m$.
The second line contains a string of length $n$ representing $a$. It is guaranteed that the string contains only 0 and 1.
The next $m$ lines each contain an operation type, followed by the operation parameters. The formats are:

1. $\ l_x\ r_x\ v$
2. $\ l_x\ r_x\ l_y\ r_y$

Output Format

For each operation of type $2$, output one integer per line representing the answer.

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

Hint

Sample Explanation

The first four levels of the tree are shown in the figure:

Operation 1: Add $5$ to the weights of all nodes in the subtree rooted at $2$.
Operation 2: Query the sum of weights on the path $2\rightarrow 10$.
Operation 3: Add $3$ to the weights of all nodes in the subtree rooted at $2$.
Operation 4: Query the sum of weights on the path $10\rightarrow 1$.
Operation 5: Query the sum of weights on the path $1\rightarrow 2$.

Constraints

This problem uses bundled testdata.

For $100\%$ of the data, $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$, and it is guaranteed that $x,y\ne 0$.

Translated by ChatGPT 5