eolymp
bolt
Try our new interface for solving problems
Problems

XOR-ing Murad

XOR-ing Murad

Time limit 2 seconds
Memory limit 128 MiB

Murad likes XOR operation very much. All the day he calculates the XOR of different numbers.

Now Murad has the next problem. He is given array a of size n. Murad must answer q queries. The queries can be of two types:

  1. 1 l r - in this query on a segment [l, r] (1l < rn) you need to find the sum of all pairwise XOR, that is, the value

xorimg.png
  1. 2 l r v - in this query on a segment [l, r] (1lrn) you need to XOR all elements with v.

Warning: here XOR is a bit operation xor.

Input data

First line contains two numbers n and q (2n2 * 10^5, 1q10^5) - the size of array and the number of queries. Next line contains the array elements a[i] (0a[i]10^9).

Next q lines contains the queries. First comes the query type, the number 1 or 2. If the query of type 1, then given two numbers l and r (1l < rn). If the query of type 2, then given three numbers l, r and v (1lrn, 0v10^9).

Output data

Print the answers to the query of type 1.

Examples

Input example #1
3 3
1 2 3
1 1 3
2 1 3 2
1 1 2
Output example #1
6
3
Input example #2
4 6
4 8 7 8
1 2 4
2 1 2 2
1 3 4
2 1 1 8
1 1 3
1 1 4
Output example #2
30
15
26
49
Author Rashad Mammadov
Source 2019 İOİ Selection Round of Azerbaijan team