Cho mảng ~a~ gồm ~n~ phần tử được đánh số từ ~1~ đến ~n~ và ~q~ truy vấn online thuộc một trong hai loại:

1. Cho ~k, x~, gán ~a_k \leftarrow x~.

2. Cho ~l, r, p~, tính tổng XOR~^\dagger~ đoạn con ~a_l, a_{l+1}, \dots, a_r~ ngay sau truy vấn thứ ~p~.

Yêu cầu: Với mỗi truy vấn loại 2, in ra kết quả cần tìm.

~\dagger~ Tổng XOR của một dãy số ~b_1, b_2, \dots b_m~ là ~b_1 \oplus b_2 \oplus \dots \oplus b_m~ với ~\oplus~ là phép bitwise XOR.

Input

Dòng đầu tiên chứa hai số nguyên ~n, q, t~ là kích thước mảng ~a~, số lượng truy vấn và hằng số để mã hóa các truy vấn online.

Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (với ~0 \leq a_i \leq 10^9~) mô tả mảng ~a~.

Trong ~q~ dòng tiếp theo, mỗi dòng mô tả một truy vấn:

• Đối với truy vấn loại 1, dòng đó chứa ba số nguyên ~1 \space k' \space x'~. Khi đó, hai giá trị ~k, x~ có thể được khôi phục bằng công thức:

  $$\begin{align} k &= k' \oplus (t \cdot ans^2) \\ x &= x' \oplus (t \cdot ans^2) \end{align}$$

  với ~0 \leq k', x' < 2^{63}~, ~1 \leq k \leq n~ và ~0 \leq x \leq 10^9~.

• Đối với truy vấn loại 2, dòng đó chứa bốn số nguyên ~2 \space l' \space r' \space p'~. Khi đó ba giá trị ~l, r, p~ có thể được khôi phục bằng công thức:

  $$\begin{align} l &= l' \oplus (t \cdot ans^2) \\ r &= r' \oplus (t \cdot ans^2) \\ p &= p' \oplus (t \cdot ans^2) \\ \end{align}$$

  với ~0 \leq l', r', p' < 2^{63}~, ~1 \leq l \leq r \leq n~, ~p < i~ và ~i~ là thứ tự của truy vấn hiện tại.

Ở đây, ~\oplus~ là kí hiệu của phép bitwise XOR, ~ans~ là kết quả của truy vấn loại 2 gần nhất, ban đầu, ~ans = 0~.

Output

Với mỗi truy vấn loại 2, in ra kết quả trên một dòng.

Scoring

• Subtask ~1~ (chiếm ~20\%~): ~1 \leq n, q \leq 2000~; ~0 \leq t \leq 1~.

• Subtask ~2~ (chiếm ~20\%~): ~1 \leq n, q \leq 2 \cdot 10^5~; ~t = 0~.

• Subtask ~3~ (chiếm ~60\%~): ~1 \leq n, q \leq 2 \cdot 10^5~; ~t = 1~.

Sample Input 1

10 7 0
16 3 9 4 11 0 12 2 10 13
1 3 8
1 2 19
2 5 5 1
2 1 8 1
2 3 5 3
1 1 7
2 4 9 1

Sample Output 1

11
26
7
11