Description

Given $n$ trash bins, you need to maintain a data structure that supports the following operations:

• 1 pos val means changing the label in the $pos$-th trash bin to $val$.

• 2 l r asks whether there exist two trash bins in $[l\oplus cnt, r\oplus cnt]$ whose labels sum to $w$.

Here, $\oplus$ denotes the XOR operation, and $cnt$ is the number of answers equal to Yes before this query.

For each operation of type 2, output Yes if such a pair exists; otherwise output No.

Note that for all queries, $w$ is the same number.

Input Format

The first line contains three integers $n, m, w$, representing the length of the sequence, the number of subsequent operations, and $w$.

The second line contains $n$ integers $a_1, a_2, \cdots, a_n$, describing the label $a$ in each trash bin.

The next $m$ lines each contain three integers in the format opt x y.

Output Format

Let the number of type 2 operations be $t$. Output $t$ lines in total.

The $i$-th line is the result of the $i$-th type 2 operation, i.e., Yes or No.

6 4 6
1 3 2 5 5 6
2 1 4
1 4 1
2 0 5
2 3 7

Yes
No
Yes

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

Yes
No
No
No
Yes
Yes

Hint

This problem uses bundled tests, with O2 optimization enabled.

$\text{Subtask 1 (7 pts)}:$ Guaranteed $1 \le n, m, w \le 2\cdot10^3$, time limit $1\text{s}$.

$\text{Subtask 2 (20 pts)}:$ Guaranteed $1 \le n, m, w \le 1\cdot10^5$, $opt = 2$, time limit $2\text{s}$.

$\text{Subtask 3 (30 pts)}:$ Guaranteed $1 \le n, m, w \le 1\cdot10^5$, time limit $2\text{s}$.

$\text{Subtask 4 (43 pts)}:$ No special restrictions, time limit $4\text{s}$.

For all testdata, $1 \le n, m, w \le 5\cdot10^5$, $0 \le a_i \le w$.

The testdata guarantees that for each operation, $1 \le pos \le n$, $0 \le val \le w$, and $1 \le l \oplus cnt \le r \oplus cnt \le n$.

Since the input and output are large, faster I/O methods are recommended.

Explanation for Sample Input #1

In the first operation, we query whether there are two numbers in the interval $[1, 4]$ that sum to $6$. Obviously, $a_1 + a_4 = 6$, so output Yes.

In the second operation, modify $a_4$ to $1$, so the sequence becomes $[1, 3, 2, 1, 5, 6]$.

In the third operation, query whether there are two numbers in the interval $[1, 4]$ that sum to $6$. There are none, so output No.

In the fourth operation, query whether there are two numbers in the interval $[2, 6]$ that sum to $6$. Obviously, $a_4 + a_5 = 6$, so output Yes.

Translated by ChatGPT 5