Mystical Binary Patterns

In ancient times, the I Ching (易经) revealed the mysterious and profound changes of the world through 64 hexagrams, each composed of six lines (爻) indicating yin (0) or yang (1). In a similar spirit, mzf has devised an enhanced divination system. He produces n unusual patterns, each having 20 rows. Every row is either a yin line (0) or a yang line (1), and thus each pattern can be viewed as a 20-bit binary string.

After drawing these n patterns on a magical parchment, mzf performs m operations. The operations are defined as follows:

• Operation 1: Reverse the order of the patterns in the interval [l, r]. For example, if the sequence is (3,1,2,5), after reversing it becomes (5,2,1,3).
• Operation 2: Magically modify each pattern in the interval [l, r] by taking a bitwise XOR with a newly drawn pattern (provided as a 20-bit binary string). That is, for every pattern in the range, update it as:
  $$a_i = a_i \oplus x,$$ where $$x$$ is the binary value of the new pattern.
• Operation 3: Query the sum of the weights of the patterns in the interval [l, r]. Here, the weight of a pattern is its equivalent integer value when the 20-bit binary string is interpreted as a binary number. (Note that a binary string such as 00000000000000000010 corresponds to the decimal value 2.)

Your task is to process all m operations in order. For each operation 3, print the required sum. Beware: if you answer any query incorrectly, catastrophic feng shui disturbances await!

inputFormat

The input begins with two integers n and m (1 ≤ n, m ≤ 10⁵).
Then follow n lines, each containing a 20-character string of 0's and 1's representing a pattern (the rows from top to bottom).
Then m operations follow. Each operation is in one of the following formats:

• For Operation 1: 1 l r
• For Operation 2: 2 l r x, where x is a 20-character binary string.
• For Operation 3: 3 l r

Indices are 1-indexed.

outputFormat

For each operation of type 3, output the sum of the weights of the patterns in the given interval on a new line.

sample

3 4
00000000000000000000
00000000000000000001
00000000000000000010
3 1 3
1 1 2
3 1 3
2 2 3 00000000000000000011
3 1 3

3
3
5