Salvage Humankind

There are n rocks in a row, with masses m[i]. Operation 1 queries the total mass of the closed interval [s,e] and outputs it; operation 2 applies bitwise XOR (^) with z to the mass of every rock in the interval, and the change persists for later operations. Ranges are numbered starting from 1.

输入格式

The first line contains n (1≤n≤100000); the second line contains n masses m[i] (0≤m[i]≤1000000); the third line contains ops (1≤ops≤50000); then ops lines follow: 1 s e denotes a query, and 2 s e z denotes an element-wise XOR update (1≤s≤e≤n, 1≤z≤1000000).

输出格式

For each type 1 operation, output one line with the total mass of the interval. The total may exceed the 32-bit integer range.

样例 1

输入：

4
1 5 2 4
3
1 1 4
2 2 3 4
1 1 4

输出：

12
12

样例 2

输入：

5
10 6 1 9 2
3
1 1 5
2 1 3 8
1 2 4

输出：

28
32

样例说明

Example 1: the initial total is 12; after XORing items 2 through 3 with 4, the array is [1,1,6,4], and the total is still 12. Example 2: the initial total is 28; after XORing the first 3 items with 8, the array is [2,14,9,9,2], and querying items 2 through 4 gives 32.