{"raw_statement":[{"iden":"background","content":"#### 注意：此题 Sub #4 中 $opt_i=3$，可视作 $opt_i=0$。数据将稍后修复，修复后将另行通知。\n\n#### UPD: 已修复。"},{"iden":"statement","content":"**题意简述**\n\n有一长度为 $k+1$ 的数组 $s$，下标依次为 $0$ 到 $k$，初始时有 $s_i = 0 \\ (0 \\leqslant i \\leqslant k)$。\n接下来给定 $n$ 个非负整数二元组 $(l_i,\\ r_i)$，记 $T = \\bigcup\\limits_{i = 1}^n [l_i,\\ r_i] $，将所有符合 $i \\in T \\bigcap \\mathbb{Z}$ 的 $s_i$ 赋值为 $1$。\n在任意时刻，记 $S =\\{ x |x \\in \\mathbb{Z} \\bigwedge x \\in [0,\\ k] \\bigwedge s_x = 0 \\}$。接下来给定 $m$ 个非负整数三元组 $(opt_i,\\ a_i,\\ b_i)$。\n\n当 $opt_i = 0$ 时，求：\n\n$$t_i = \\sum\\limits_{x = a_i}^{b_i} \\min\\limits_{y \\in S}(x \\oplus y)$$\n\n当 $opt_i = 1$ 时，将所有符合 $i \\in [a_i,\\ b_i] \\bigcap \\mathbb{Z}$ 的 $s_i$ 赋值为 $1$。\n\n当 $opt_i = 2$ 时，将所有符合 $i \\in [a_i,\\ b_i] \\bigcap \\mathbb{Z}$ 的 $s_i$ 赋值为 $0$。\n\n符号 $\\mathbb{Z}$ 表示全体整数，$\\oplus$ 表示异或。\n\n---\n\n**原版题面**\n\n『斑马王子』统治着无垠的草原。\n\n一条小河无息地流淌在草原的中央，与河流源头距离为 $y$ 的草地被赋予了 $y \\ (0 \\leqslant y \\leqslant k)$ 的『膜力』。\n\n第 $x \\ (0 \\leqslant x \\leqslant k)$ 天，『斑马王子』的『潜力智商』为 $x$。\n\n他会来到一片自己心仪的草地用膳，并以 $x \\oplus y$ 的『智商』开始新的一天。\n\n有一种叫『猎人』的生物，热衷于剥夺草原居民的生命。\n\n他们初始时设立了 $n$ 个形如 $(l_i,\\ r_i) \\ (0 \\leqslant l_i \\leqslant r_i \\leqslant k)$ 的营地，用『枪』屠杀着所有在 $[l_i,\\ r_i]$ 中驻足的生灵。\n\n作为『斑马王子』的得力大臣，你需要回答他的若干个问题，以保证草原的安全。\n\n在风云变幻的草原上，会依次发生 $m$ 个形如 $(opt_i,\\ a_i,\\ b_i) \\ (0 \\leqslant a_i \\leqslant b_i \\leqslant k , \\ opt_i \\in \\{0,\\ 1,\\ 2\\})$ 的事件。\n\n当 $opt_i = 1$ 时，事件 $i$ 代表猎人在 $[a_i,\\ b_i]$ 中全部驻扎了新营地。\n\n当 $opt_i = 2$ 时，事件 $i$ 代表斑马王子英勇的部队摧毁了 $[a_i,\\ b_i]$ 中的全部营地。\n\n而当 $opt_i = 0$ 时，斑马王子向你发出了灵魂拷问：\n\n每一个问题中，『斑马王子』希望从第 $a_i$ 到第 $b_i$ 天 $(0 \\leqslant a_i \\leqslant b_i \\leqslant k)$，在非『猎人』营地的草地用膳。『斑马王子』希望知道从第 $a_i$ 到 $b_i$ 天，『智商』之和的最小可能值 $t_i$。\n\n你苦思冥想，忽然，『枪』的吼叫声撕裂了空气，如果不在 $1 \\ sec$ 内回答问题 $\\dots \\dots$"},{"iden":"input","content":"第一行输入整数 $n, \\ m, \\ k$。\n\n接下来 $n$ 行，每行两个整数 $l_i, \\ r_i$，表示『猎人』的一个营地。\n\n接下来 $m$ 行，每行三个整数 $opt_i,\\ a_i,\\ b_i$，表示一组操作。"},{"iden":"output","content":"对于第 $i$ 组操作 $(1 \\leqslant i \\leqslant m)$，当 $opt_i = 1$ 或 $opt_i = 2$ 时，不需要输出。\n\n当 $opt_i = 0$ 时，当所有草地都属于猎人的营地时，输出一行 ``Death``,否则输出一行一个整数，表示 $t_i$。"},{"iden":"note","content":"**数据范围**\n\n**本题采用捆绑测试。**\n\n$\\texttt{Subtask 1 (5 pts)}$：对于 $5\\%$ 的数据，保证 $0 \\leqslant n,m,k \\leqslant 20$。\n\n$\\texttt{Subtask 2 (5 pts)}$：对于 $5\\%$ 的数据，保证 $0 \\leqslant n,m,k \\leqslant 500$。\n\n$\\texttt{Subtask 3 (15 pts)}$：对于 $15\\%$ 的数据，保证 $0 \\leqslant n,m,k \\leqslant 4000$。\n\n$\\texttt{Subtask 4 (5 pts)}$：对于 $5\\%$ 的数据，保证 $opt_i = 0$。\n\n$\\texttt{Subtask 5 (70 pts)}$：无特殊限制。\n\n对于 $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\\}$。"}],"translated_statement":null,"sample_group":[["0 16 3\n0 0 3\n1 3 3\n0 0 3\n1 1 2\n0 0 3\n2 1 3\n0 0 3\n1 0 0\n1 1 1\n0 0 3\n0 1 2\n0 1 3\n1 2 3\n0 2 3\n2 3 3\n0 2 3","0\n1\n6\n0\n4\n2\n2\nDeath\n1"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}