XOR on Segment

Source: Codeforces

Version: Phuoc Hung OJ Extended

Problem Statement

Maintain an integer array under range-sum queries and range XOR updates by a common mask.

Input

The first line contains $n$, the second the initial array, and the third $m$. Each operation is:

• 1 l r: print the sum on $[l,r]$.
• 2 l r x: replace every $a_i$ in $[l,r]$ by $a_i\mathbin{\oplus}x$.

Output

Print the sum for every type 1 query.

Subtasks

• 20 points: $n,m\le50$.
• 30 points: $n,m\le5000$.
• 50 points: $n\le10^5$, $m\le5\cdot10^4$, $0\le a_i\le10^6$, $1\le x\le10^6$.

Examples

Input

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

Output

26
22
0
34
11

Explanation

The first sum is $10+3+13=26$. Each XOR update flips exactly the bit positions present in mask $x$; processing all operations yields the later sums 22, 0, 34, and 11.