Infinite Binary Tree Queries

You are given an infinite binary tree with the following properties:

• The tree has infinitely many nodes.
• Each node has a unique number and an associated weight. Initially all weights are \(0\).
• The root has number \(1\).
• For a node numbered \(i\), its left child is numbered \(2i\) and its right child is numbered \(2i+1\).

There will be \(m\) operations on the tree. Each operation is one of the following two types:

1. Update: For a given node \(x\), add an integer \(v\) to the weight of every node in the subtree rooted at \(x\).
2. Query: Given two nodes \(x\) and \(y\), compute the sum of the weights of every node on the unique simple path from \(x\) to \(y\), outputting the answer modulo \(2^{32}\).

However, the values \(x\) and \(y\) are not provided directly. Instead, you are given a binary string \(a\) of length \(n\) consisting of characters '0' and '1'. For an update operation, the node \(x\) is determined by an interval \([l, r]\) of \(a\): interpret the substring \(a[l\ldots r]\) (1-indexed) as a binary number. Similarly for a query, two intervals \([l_x, r_x]\) and \([l_y, r_y]\) are given to determine \(x\) and \(y\) respectively.

Input Format: The input begins with a line containing two integers \(m\) and \(n\). The next line contains the binary string \(a\) of length \(n\). Then \(m\) lines follow, each describing an operation.

For an update operation, the line is in the format:

1 l r v

Here, the node \(x\) is calculated as \(x = \text{value}(a[l\ldots r])\) in base 2 and \(v\) is the value to add.

For a query operation, the line is in the format:

2 l_x r_x l_y r_y

The nodes \(x\) and \(y\) are computed from the intervals \([l_x, r_x]\) and \([l_y, r_y]\) respectively. You are to output the sum of the weights of all nodes on the unique path from \(x\) to \(y\) modulo \(2^{32}\).

inputFormat

The first line contains two integers \(m\) and \(n\): the number of operations and the length of the binary string \(a\), respectively.

The second line contains a binary string \(a\) of length \(n\) (consisting only of '0' and '1').

Then, \(m\) lines follow. Each of these lines represents an operation in one of the following formats:

• Update Operation: 1 l r v. Here, the node \(x\) is determined by interpreting the substring \(a[l...r]\) (1-indexed) as a binary number, and \(v\) is the integer value to add to each node in the subtree rooted at \(x\).
• Query Operation: 2 l_x r_x l_y r_y. Here, the nodes \(x\) and \(y\) are computed from the substrings \(a[l_x...r_x]\) and \(a[l_y...r_y]\) respectively. You should output the sum of weights on the path from \(x\) to \(y\) modulo \(2^{32}\).

outputFormat

For each query operation, output a single line containing one integer: the sum of the weights on the path between the two specified nodes, taken modulo \(2^{32}\).

sample

5 8
10101010
1 1 3 5
2 1 3 2 4
1 5 8 3
2 3 4 5 6
2 1 8 1 8

5
0
0

</p>