Read problems statements in Mandarin chinese, Russian and Vietnamese as well.

Chef always likes to play with arrays. He came up with a new term "magical subarray". A subarray is called magical if its starting index is 1 (1-based indexing). Now, Chef has an array of N elements and 2 types of queries:

type 1: Given two numbers i and x, the value at index i should be updated to x.
type 2: Given two numbers i and k, your program should output the total number of magical subarrays with the last index ≤ i in which the xor of all elements is equal to k.

------ Input ------

The first line of the input contains two integers N and Q denoting the number of elements in the array and the number of queries respectively.
The second line contains N space-separated integers A_{1}, A_{2} ... A_{N} denoting the initial values of the array.
Each of the following Q lines describes an operation. If the first integer is 1, it means that the operation is of type 1 and it will be followed by two integers i and x. If the first integer is 2, it means that the operations is of type 2 and it will be followed by two integers i and k.

------ Output ------

For each operation of type 2, print the number of magical subarrays on a separate line.

------ Constraints ------

$1 ≤ N, Q ≤ 100,000$
$1 ≤ A[i] ≤ 1,000,000$
$1 ≤ i ≤ N$
$1 ≤ x, k ≤ 1,000,000$

------ Subtasks ------

Subtask #1 (20 points): 1 ≤ N, Q ≤ 1,000

Subtask #2 (30 points): 1 ≤ N, Q ≤ 10,000

Subtask #3 (50 points): original constraints

----- Sample Input 1 ------
5 3
1 1 1 1 1
2 5 1
1 3 2
2 5 1
----- Sample Output 1 ------
3
1

见题面

见题面