[CoE R5] 斑马王子

#### 注意：此题 Sub #4 中 $opt_i=3$，可视作 $opt_i=0$。数据将稍后修复，修复后将另行通知。 #### UPD: 已修复。

**题意简述** 有一长度为 $k+1$ 的数组 $s$，下标依次为 $0$ 到 $k$，初始时有 $s_i = 0 \ (0 \leqslant i \leqslant k)$。 接下来给定 $n$ 个非负整数二元组 $(l_i,\ r_i)$，记 $T = \bigcup\limits_{i = 1}^n [l_i,\ r_i] $，将所有符合 $i \in T \bigcap \mathbb{Z}$ 的 $s_i$ 赋值为 $1$。 在任意时刻，记 $S =\{ x |x \in \mathbb{Z} \bigwedge x \in [0,\ k] \bigwedge s_x = 0 \}$。接下来给定 $m$ 个非负整数三元组 $(opt_i,\ a_i,\ b_i)$。 当 $opt_i = 0$ 时，求： $$t_i = \sum\limits_{x = a_i}^{b_i} \min\limits_{y \in S}(x \oplus y)$$ 当 $opt_i = 1$ 时，将所有符合 $i \in [a_i,\ b_i] \bigcap \mathbb{Z}$ 的 $s_i$ 赋值为 $1$。 当 $opt_i = 2$ 时，将所有符合 $i \in [a_i,\ b_i] \bigcap \mathbb{Z}$ 的 $s_i$ 赋值为 $0$。 符号 $\mathbb{Z}$ 表示全体整数，$\oplus$ 表示异或。 --- **原版题面** 『斑马王子』统治着无垠的草原。 一条小河无息地流淌在草原的中央，与河流源头距离为 $y$ 的草地被赋予了 $y \ (0 \leqslant y \leqslant k)$ 的『膜力』。 第 $x \ (0 \leqslant x \leqslant k)$ 天，『斑马王子』的『潜力智商』为 $x$。 他会来到一片自己心仪的草地用膳，并以 $x \oplus y$ 的『智商』开始新的一天。 有一种叫『猎人』的生物，热衷于剥夺草原居民的生命。 他们初始时设立了 $n$ 个形如 $(l_i,\ r_i) \ (0 \leqslant l_i \leqslant r_i \leqslant k)$ 的营地，用『枪』屠杀着所有在 $[l_i,\ r_i]$ 中驻足的生灵。 作为『斑马王子』的得力大臣，你需要回答他的若干个问题，以保证草原的安全。 在风云变幻的草原上，会依次发生 $m$ 个形如 $(opt_i,\ a_i,\ b_i) \ (0 \leqslant a_i \leqslant b_i \leqslant k , \ opt_i \in \{0,\ 1,\ 2\})$ 的事件。 当 $opt_i = 1$ 时，事件 $i$ 代表猎人在 $[a_i,\ b_i]$ 中全部驻扎了新营地。 当 $opt_i = 2$ 时，事件 $i$ 代表斑马王子英勇的部队摧毁了 $[a_i,\ b_i]$ 中的全部营地。 而当 $opt_i = 0$ 时，斑马王子向你发出了灵魂拷问： 每一个问题中，『斑马王子』希望从第 $a_i$ 到第 $b_i$ 天 $(0 \leqslant a_i \leqslant b_i \leqslant k)$，在非『猎人』营地的草地用膳。『斑马王子』希望知道从第 $a_i$ 到 $b_i$ 天，『智商』之和的最小可能值 $t_i$。 你苦思冥想，忽然，『枪』的吼叫声撕裂了空气，如果不在 $1 \ sec$ 内回答问题 $\dots \dots$

第一行输入整数 $n, \ m, \ k$。 接下来 $n$ 行，每行两个整数 $l_i, \ r_i$，表示『猎人』的一个营地。 接下来 $m$ 行，每行三个整数 $opt_i,\ a_i,\ b_i$，表示一组操作。

对于第 $i$ 组操作 $(1 \leqslant i \leqslant m)$，当 $opt_i = 1$ 或 $opt_i = 2$ 时，不需要输出。 当 $opt_i = 0$ 时，当所有草地都属于猎人的营地时，输出一行 ``Death``,否则输出一行一个整数，表示 $t_i$。

0 16 3
0 0 3
1 3 3
0 0 3
1 1 2
0 0 3
2 1 3
0 0 3
1 0 0
1 1 1
0 0 3
0 1 2
0 1 3
1 2 3
0 2 3
2 3 3
0 2 3

0
1
6
0
4
2
2
Death
1

**数据范围** **本题采用捆绑测试。** $\texttt{Subtask 1 (5 pts)}$：对于 $5\%$ 的数据，保证 $0 \leqslant n,m,k \leqslant 20$。 $\texttt{Subtask 2 (5 pts)}$：对于 $5\%$ 的数据，保证 $0 \leqslant n,m,k \leqslant 500$。 $\texttt{Subtask 3 (15 pts)}$：对于 $15\%$ 的数据，保证 $0 \leqslant n,m,k \leqslant 4000$。 $\texttt{Subtask 4 (5 pts)}$：对于 $5\%$ 的数据，保证 $opt_i = 0$。 $\texttt{Subtask 5 (70 pts)}$：无特殊限制。 对于 $100 \%$ 的数据， $0 \leqslant n,\ m,\ k \leqslant 2 \times 10^5$，$0 \leqslant l_i \leqslant r_i \leqslant k$，$0 \leqslant a_i \leqslant b_i \leqslant k$，$opt_i \in \{0,\ 1,\ 2\}$。