Cho một dãy ~a~ gồm ~n~ số nguyên không âm ~a_1, a_2, \ldots , a_n~. Có hai loại truy vấn sau đây:

1. Tính tổng đoạn con từ ~l~ đến ~r~ trong mảng ~a~ hiện tại ~(a_l + a_{l+1} + \ldots + a_r)~.

2. Thực hiện phép toán xor với ~x~ cho các phần tử nằm trong đoạn con từ ~l~ đến ~r~ ~(a_l = a_l \oplus x, a_{l+1} = a_{l+1} \oplus x, \ldots , a_r = a_r \oplus x)~.

Cho trước dãy số ~a~ và ~m~ truy vấn. Bạn hãy thực hiện các phép truy vấn này, và in ra kết quả đối với loại truy vấn ~1~.

Dữ liệu

• Dòng đầu tiên gồm một số nguyên dương ~n~ ~(1 \le n \le 10^5)~.

• Dòng thứ hai gồm ~n~ số nguyên không âm ~a_1, a_2, \ldots, a_n~ ~(0 \le a_i \le 10^6)~.

• Dòng thứ ba gồm một số nguyên dương ~m~ ~(1 \le m \le 5 \cdot 10^4)~.

• ~m~ dòng tiếp theo thuộc một trong hai loại truy vấn sau:

  • 1 l r ~(1 \le l \le r \le n)~.

  • 2 l r x ~(1 \le l \le r \le n,\ 1 \le x \le 10^6)~.

Kết quả

• Với mỗi truy vấn loại ~1~, in ra kết quả là tổng của đoạn con tương ứng. Lưu ý các kết quả được in theo đúng thứ tự dữ liệu được nhập vào.

Ràng buộc

• Subtask 1 (60%): ~1 \le n, m \le 1000~.

• Subtask 2 (40%): ~1 \le n \le 10^5;\ 1 \le m \le 5 \cdot 10^4~.

Ví dụ

Sample Input 1

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

Sample Output 1

7
33
6

Sample Input 2

7
45 98 12 65 74 32 44
5
1 1 7
2 2 5 4
2 5 7 7
1 1 3
1 4 5

Sample Output 2

370
155
142