Cho dãy \(a\) gồm \(n\) số nguyên dương \(a_1, a_2, a_3, \dots, a_n\).
Có \(3\) loại truy vấn:

• \(1\ k\ x\): Tăng \(a_k\) lên \(x\) đơn vị (\(1 \leq x \leq 10^9\)).
• \(2\ k\ x\): Đặt \(a_k = a_k\) XOR \(x\).
• \(3\ l\ r\): Đếm số lượng số nguyên \(k\) (\(l \leq k \leq r\)) mà \(a_l \text{ XOR } a_{l+1} \text{ XOR } a_{l+2} \text{ XOR } \dots \text{ XOR } a_k\) là số lẻ.

Input

• Dòng đầu tiên nhập vào hai số nguyên dương \(n, q\) - lần lượt là số phần tử dãy \(a\) và số lượng truy vấn.
• Dòng thứ hai là \(n\) số nguyên dương \(a_1, a_2, a_3, \dots, a_n\) (\(1 \leq a_i \leq 10^9\) với mọi \(1 \leq i \leq n\)).
• \(q\) dòng tiếp theo, mỗi dòng nhập ba số nguyên là một trong ba truy vấn loại trên.

Output

• Với mỗi truy vấn loại \(3\), hãy in ra kết quả theo yêu cầu của đề bài.

Example

5 5
1 4 5 8 9
3 1 5
1 2 3
3 1 5
2 3 9
3 1 5

3
3
2

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n \leq 10^4, q \leq 10^3\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \leq 10^6, q \leq 10^6\). Chỉ bao gồm các truy vấn loại \(3\).
• Subtask \(3\) (\(30\%\) số điểm): \(n \leq 10^6, q \leq 10^6\).