题目背景

也许，同学间最好的结局就是朋友吧。

$\mu ry$ 是一个可爱的女孩子。

在她所住的小区里有排成一排的 $n$ 个垃圾桶，从左至右第 $i$ 个垃圾桶里都装着编号为 $a_i$ 的垃圾。

$\mu ry$ 不喜欢无序，于是就想把社区里编号和为 $w$ 的垃圾都清在一起。

但是调皮的 $\text{LeverImmy}$ 可能会把某个垃圾桶里的垃圾偷换成另一种。

生气的 $\mu ry$ 想考考 $\text{LeverImmy}$ 一个区间 $[l, r]$ 内是否存在编号和为 $w$ 的垃圾。

但 $\text{LeverImmy}$ 也不会解决这个问题，于是他找到了聪明的你。

题目描述

给定 $n$ 个垃圾桶，你需要维护一个数据结构，支持以下操作：

• 1 pos val 表示将 第 $pos$ 个垃圾桶里的垃圾的编号换成 $val$；

• 2 l r 询问在 $[l\oplus cnt, r\oplus cnt]$ 内是否存在垃圾编号和为 $w$ 的 两个 垃圾桶。

其中 $\oplus$ 表示异或运算，$cnt$ 表示在 此次询问之前，答案为 Yes 的个数。

对于每个操作 2，若存在请输出 Yes，不存在请输出 No。

值得注意的是，对于所有询问， $w$ 为 同一个数。

输入格式

第一行共三个整数 $n, m, w$，表示序列长度、接下来的操作个数与 $w$。

第二行共 $n$ 个整数 $a_1, a_2, \cdots, a_n$ 描述了这个每个垃圾桶内垃圾的编号 $a$。

接下来的 $m$ 行，每行三个整数，格式为 opt x y。

输出格式

令操作 2 的次数为 $t$，输出数据共 $t$ 行。

第 $i$ 行表示第 $i$ 个操作 2 的结果，即 Yes 或 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

提示

本题采用 捆绑测试，开启 O2优化。

$\text{Subtask 1 (7 pts)}:$ 保证 $1 \le n, m, w \le 2\cdot10^3$，时限 $1\text{s}$；

$\text{Subtask 2 (20 pts)}:$ 保证 $1 \le n, m, w \le 1\cdot10^5$，$opt = 2$，时限 $2\text{s}$；

$\text{Subtask 3 (30 pts)}:$ 保证 $1 \le n, m, w \le 1\cdot10^5$，时限 $2\text{s}$；

$\text{Subtask 4 (43 pts)}:$ 没有特殊限制，时限 $4\text{s}$；

对于所有数据， $1 \le n, m, w \le 5\cdot10^5$，$0 \le a_i \le w$。

数据保证对于每个操作，$1 \le pos \le n$，$0 \le val \le w$，$1 \le l \le r \le n$。

由于输入输出量较大，建议使用更快的输入输出方式。

---

输入 #1 解释

第一次操作，询问区间 $[1, 4]$ 中是否有两个数加起来为 $6$，显然有$a_1 + a_4 = 6$，因此输出 Yes；

第二次操作，修改 $a_4$ 为 $1$，则序列变为 $[1, 3, 2, 1, 5, 6]$；

第三次操作，询问区间 $[1, 4]$ 中是否有 两个 数加起来为 $6$，无，因此输出 No。

第四次操作，询问区间 $[2, 6]$ 中是否有两个数加起来为 $6$，显然有 $a_4 + a_5 = 6$，因此输出 Yes。