Truy vấn XOR

Bạn có một mảng \(a\) , gồm \(n\) số nguyên \(a_{1} , a_{2} , ..., a_{n}\) . Bạn được phép thực hiện hai thao tác trên mảng này:

• Tính tổng các phần tử mảng hiện tại trên đoạn \([l,r]\) , nghĩa là tính \(a_{l} + a_{l + 1} + ... + a_{r}\).

• Áp dụng phép toán xor với một số \(x\) cho trước cho mỗi phần tử của mảng trên đoạn \([l,r]\) , nghĩa là \(a_{i}:=a_{i}\) \(xor\) \(x\) với \(l \leq i \leq r\). Thao tác này thay đổi chính xác \(r - l + 1\) phần tử của mảng.

Bạn có một danh sách gồm \(m\) thao tác thuộc một trong hai loại trên. Nhiệm vụ của bạn là thực hiện tất cả các thao tác đã cho, đối với mỗi thao tác tính tổng, in ra kết quả của thao tác đó.

Input

Dòng đầu tiên chứa số nguyên dương \(n\) \((1 ≤ n ≤ 2.10^5)\) - kích thước của mảng.

Dòng thứ hai chứa các số nguyên không âm \(a_{1} , a_{2} , ..., a_{n}\) \((0 ≤ a_{i} ≤ 10^6)\) - mảng ban đầu.

Dòng thứ ba chứa số nguyên \(m\) \(( 1 ≤ m ≤ 2.10^5 )\) - số truy vấn.
Dòng thứ \(i\) trong số \(m\) dòng tiếp theo đầu tiên chứa số nguyên \(t_i\) \((1 ≤ t_{i} ≤ 2)\) - loại thao tác thứ i .

Nếu \(t_{i} = 1\) thì đây là thao tác tính tổng, nếu \(t_{i} = 2\) thì đây là thao tác thay đổi các phần tử mảng. Nếu thao tác thứ \(i\) thuộc loại \(1\) , thì tiếp theo là hai số nguyên \(l_{i} , r_{i}\) \(( 1 ≤ l_{i} ≤ r_{i} ≤ n )\). Nếu phép toán thứ \(i\) thuộc loại \(2\) , thì tiếp theo là ba số nguyên \(l_{i} , r_{i} , x_{i}\) \((1 ≤ l_{i} ≤ r_{i} ≤ n , 1 ≤ x_{i} ≤ 10 ^ 6 )\). Các số trên các dòng được phân tách bằng dấu cách.

Output

Với mỗi thao tác loại \(1\), in ra trên một dòng là kết quả của thao tác.

Example

5
4 10 3 13 7
8
1 2 4
2 1 3 3
1 2 4
1 3 3
2 2 5 5
1 1 5
2 1 2 10
1 2 3

26
22
0
34
11

Scoring

\(50\%\) số test tương ứng \(50\%\) số điểm có \(n, m <= 10^3\).

\(50\%\) số test tương ứng \(50\%\) số điểm còn lại không có ràng buộc gì thêm.