There are  types of operations.

Maintain a sequence of  integers , by performing  operations on it:

-  for each , replace with . Here, denotes the bitwise and operation.

-  - print the sum of all the numbers in the interval   module , that is, print .

- - undo the change made by the last operation of type  which has not been revoked. It's guaranteed that at least one operation of type not being undone exists when performing it.

有种操作。给定一个长度为  的序列 , 你需要维护  次操作:

-  对所有的 ，将  替换成 。这里，   表示位运算的与操作。

-  - 输出  区间的数的和模 。换句话说，输出 .

-  - 取消上一次还未取消的类型 的操作。保证在执行这个操作时，至少存在一个未被取消的类型  的操作。

输入描述:

The first line contains  integers  and  - the length of the sequence and the number of operations.

The next line contains  integers  separated by spaces, representing the initial sequence.
 
Then  lines follow. The -th line contains the -th operation. The format of the operation input is shown above. 

第一行包含两个整数.
第二行包含 个整数   .
接下来  行，每行一个操作，格式同题目描述。

输出描述:

For each operation of type , output a line of a single integer, representing the answer.

对于每个询问，输出每行一个整数，表示相应的答案。

10 3
1 2 3 4 5 6 7 8 9 10
1 1 10
2 1 10
3

6