题目背景

注意：此题 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\}$。