July 28th, today is a sunny day.

I carry my luggage and arrive at this island. Everything is so familiar; have I actually been here countless times before?

Following the winding streets, I arrive at an ordinary house. I know that the person I want to see is here.

I once made her bear too much. But it wasn't until I lost her that I understood all of this.

A colorful butterfly flies past me, its wings emitting a faint glow. Am I one of them?

There is no one in the house. I open the door and see a drawing diary on the floor. I open it, and in an instant, I remember a sentence someone once said: "This diary is a magic diary; everything drawn in it can come true!"

I smile slightly and close the diary. "Umi, I'm waiting for you."

Given a segment tree, this segment tree is a generalized segment tree. In a standard segment tree, for an interval $[l, r]$, we take $m = \lfloor \frac{l+r}{2} \rfloor$ and divide the interval into two sub-intervals $[l, m]$ and $[m+1, r]$. In a generalized segment tree, $m$ is not required to be exactly the midpoint of the interval, but $m$ must still satisfy $l \leq m < r$. It is not difficult to see that in a generalized segment tree, the depth of the tree can reach $O(n)$.

The following is a generalized segment tree:

We provide the split point of each node in the segment tree using a preorder traversal. For example, the following sequence represents the segment tree:

5 1 3 2 4

This means that for $[1, 6]$, the split point is $5$; for $[1, 5]$, the split point is $1$; for $[2, 5]$, the split point is $3$, and so on.

It is known that the value of each node in this segment tree is the bitwise AND of the numbers in the interval it represents. Now you need to support the following operations:

1 l r x means to perform a bitwise AND operation on all numbers in [l, r] with x, and update the segment tree
2 l r x means to perform a bitwise OR operation on all numbers in [l, r] with x, and update the segment tree
3 l r x means to perform a bitwise XOR operation on all numbers in [l, r] with x, and update the segment tree

It is guaranteed that $[l, r]$ is always an interval represented by some node in the segment tree.

4 l r means to start from the node representing [l, r]. Let the value of the current node be y. If the binary representation of y has an odd number of 1s (i.e., popcount(y)%2==1), move to the left child of the current node; otherwise, move to the right child. Continue until you cannot move further. Output the sum of the values of the nodes visited.

Input

The first line contains two positive integers $n$ and $q$, representing that the sequence maintained by this segment tree has length $n$ (the segment tree has $2n-1$ nodes) and there are $q$ operations.

The next line contains $n$ positive integers $a_i$, representing the initial values of the sequence.

The next line contains the preorder traversal of the segment tree's split points.

The next $q$ lines each contain 4 or 3 integers, representing the operations.

Output

For each query, output the answer.

Examples

Input 1

10 20
0 5 2 10 6 6 12 2 8 7
2 1 9 7 3 4 5 6 8
1 1 10 12
1 5 7 5
4 7 7
4 4 7
3 4 4 15
3 1 1 9
4 1 2
4 1 10
1 1 1 2
3 5 5 5
2 8 9 7
2 2 2 7
3 3 3 12
1 1 2 7
1 9 9 3
4 9 9
3 6 6 14
2 1 1 6
3 6 7 3
4 3 10

Output 1

4
8
4
4
3
4

Constraints

Subtask 1 (10pts) $n, q \leq 10^3$

Subtask 2 (20pts) $n, q \leq 10^5$, no modification operations

Subtask 3 (30pts) $n, q \leq 10^5$, no XOR operations

Subtask 4 (40pts) $n \leq 10^6, q \leq 10^5$, no special properties

For all data, $a_i, x \leq [0, 10^9]$, and it is guaranteed that the given interval is always one represented by a node in the segment tree.

Time limit: $4\mathtt{s}$

Memory limit: $512\mathtt{MB}$