XOR

Time limit2sMemory limit512 MB

Summary

Maintain an array under range XOR updates and point queries, printing each queried element in order.

Level: Medium6 of 10
Topics: Binary search, Prefix sum, Bit manipulation, Sorting
Solved: No attempts yet

Problem

Process two kinds of operations on a single sequence.

XOR $c$ into every element of the interval $[a, b]$ .
Print the value of the element at index $a$ .

Given the initial sequence and the list of operations, produce the result of every print operation in order.

Input

The first line contains the length of the sequence $n$ . ( $0 < n \le 500{,}000$ )

The second line contains the elements of the sequence, from index $0$ to index $n - 1$ in order. Every element is a non-negative integer no larger than $100{,}000$ .

The third line contains the number of queries $m$ . ( $0 < m \le 500{,}000$ )

Each of the next $m$ lines holds one query and starts with the query kind $t$ . If $t$ is 1, then $a$ , $b$ , and $c$ follow, and $c$ is xored into every element of the interval $[a, b]$ . ( $0 \le a \le b < n$ , $0 \le c \le 100{,}000$ ) If $t$ is 2, then $a$ follows, and the current value of the element at index $a$ is printed. ( $0 \le a < n$ )

Output

For every query with $t$ equal to 2, print the current value of the element at index $a$ on its own line.

Examples6

Example 1

Input

Expected output

Example 2

Input

1
0
5
2 0
1 0 0 100000
2 0
1 0 0 100000
2 0

Expected output

0
100000
0

Example 3

Input

4
7 0 100000 13
4
2 0
2 1
2 2
2 3

Expected output

Example 4

Input

6
0 0 0 0 0 0
9
1 0 5 12
1 1 3 0
2 0
1 2 4 5
2 2
2 3
2 4
2 5
2 1

Expected output

Example 5

Input

3
100000 100000 99999
7
1 0 2 100000
2 0
2 1
2 2
1 1 1 65535
2 1
2 2

Expected output

Example 6

Input

Expected output