Queries and Queries

Time limit2.5sMemory limit1024 MB

Summary

Given an array and M range-XOR updates, answer queries that XOR a range of update values by v and queries that XOR a range of the final array.

Level: Hard8 of 10
Topics: Segment tree, Bit manipulation, Prefix sum, Array
Solved: No attempts yet

Problem

You are given an array $A_1, A_2, \ldots, A_N$ of size $N$ . Apply the following update operation $M$ times to this array. Here $\oplus$ is the bitwise XOR operation.

$l$ $r$ $x$ : For every $A_i$ with $l \le i \le r$ , execute $A_i = A_i \oplus x$ .

Write a program that answers the following queries.

1 $L$ $R$ $v$ : For every $i$ with $L \le i \le R$ , execute $x_i = x_i \oplus v$ . Here $x_i$ is the value of $x$ in the $i$ -th update.
2 $s$ $e$ : Print $A_s \oplus A_{s+1} \oplus \cdots \oplus A_e$ in the array after all $M$ update operations have been applied.

Input

The first line contains $N$ , $M$ , and $Q$ , separated by spaces. ( $1 \le N, M, Q \le 10^5$ )

The second line contains $A_1$ through $A_N$ , separated by spaces. ( $0 \le A_i \le 10^9$ )

The next $M$ lines each contain three integers $l$ , $r$ , and $x$ , in that order. ( $1 \le l \le r \le N$ , $0 \le x \le 10^9$ )

The next $Q$ lines each contain a query, which is either 1 $L$ $R$ $v$ or 2 $s$ $e$ . ( $1 \le L \le R \le M$ , $0 \le v \le 10^9$ , $1 \le s \le e \le N$ )

Output

For each query of type 2, print the answer on its own line.

Examples1

Example 1

Input

9 8 9
22 2 20 6 20 3 22 28 7
6 9 11
3 6 9
3 4 14
4 9 30
2 4 30
2 7 22
4 7 5
1 7 29
2 2 9
2 4 5
1 5 6 2
1 1 8 22
2 2 4
2 1 3
2 4 6
1 4 5 7
2 1 3

Expected output