Background

Note: In Subtask #4 of this problem, $opt_i=3$ can be treated as $opt_i=0$. The testdata will be fixed later, and another notice will be given after the fix.

UPD: Fixed.

Problem Description

Brief statement

There is an array $s$ of length $k+1$, indexed from $0$ to $k$. Initially, $s_i = 0 \ (0 \leqslant i \leqslant k)$.

Next, you are given $n$ pairs of non-negative integers $(l_i,\ r_i)$. Let $T = \bigcup\limits_{i = 1}^n [l_i,\ r_i]$. Set all $s_i$ with $i \in T \bigcap \mathbb{Z}$ to $1$.

At any moment, define $S =\{ x \mid x \in \mathbb{Z} \wedge x \in [0,\ k] \wedge s_x = 0 \}$. Then you are given $m$ triples of non-negative integers $(opt_i,\ a_i,\ b_i)$.

• When $opt_i = 0$, compute:

$$t_i = \sum\limits_{x = a_i}^{b_i} \min\limits_{y \in S}(x \oplus y)$$

• When $opt_i = 1$, set all $s_i$ with $i \in [a_i,\ b_i] \bigcap \mathbb{Z}$ to $1$.

• When $opt_i = 2$, set all $s_i$ with $i \in [a_i,\ b_i] \bigcap \mathbb{Z}$ to $0$.

Here, $\mathbb{Z}$ denotes the set of all integers, and $\oplus$ denotes XOR.

---

Original story statement

The “Zebra Prince” rules over the boundless grassland.

A small river flows quietly through the center of the grassland. A piece of grassland at distance $y$ from the river source is given “membrane power” (mo li, 膜力) of value $y \ (0 \leqslant y \leqslant k)$.

On day $x \ (0 \leqslant x \leqslant k)$, the Zebra Prince’s “potential IQ” is $x$.

He will go to a grassland he likes to dine, and start a new day with “IQ” equal to $x \oplus y$.

There is a kind of creature called “hunters”, who love to take away the lives of grassland residents.

Initially, they set up $n$ camps of the form $(l_i,\ r_i) \ (0 \leqslant l_i \leqslant r_i \leqslant k)$, and use “guns” to kill all living beings that stop within $[l_i,\ r_i]$.

As the Zebra Prince’s capable minister, you need to answer some of his questions to keep the grassland safe.

On this ever-changing grassland, $m$ events of the form $(opt_i,\ a_i,\ b_i) \ (0 \leqslant a_i \leqslant b_i \leqslant k , \ opt_i \in \{0,\ 1,\ 2\})$ will happen in order.

When $opt_i = 1$, event $i$ means the hunters have set up new camps everywhere in $[a_i,\ b_i]$.

When $opt_i = 2$, event $i$ means the Zebra Prince’s brave army has destroyed all camps in $[a_i,\ b_i]$.

When $opt_i = 0$, the Zebra Prince asks you a soul-searching question:

In each query, from day $a_i$ to day $b_i$ $(0 \leqslant a_i \leqslant b_i \leqslant k)$, the Zebra Prince wants to dine on grasslands that are not “hunter” camps. He wants to know the minimum possible value $t_i$ of the sum of “IQ” from day $a_i$ to day $b_i$.

You rack your brain. Suddenly, the roar of “guns” tears the air apart. If you cannot answer within $1 \ sec$…

Input Format

The first line contains integers $n, \ m, \ k$.

The next $n$ lines each contain two integers $l_i, \ r_i$, describing one hunter camp.

The next $m$ lines each contain three integers $opt_i,\ a_i,\ b_i$, describing one operation.

Output Format

For the $i$-th operation $(1 \leqslant i \leqslant m)$:

• If $opt_i = 1$ or $opt_i = 2$, you do not need to output anything.
• If $opt_i = 0$, then if all grasslands belong to hunter camps, output one line Death. Otherwise, output one line with an integer, representing $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

Hint

Constraints

This problem uses bundled tests.

$\texttt{Subtask 1 (5 pts)}$: For $5\%$ of the data, $0 \leqslant n,m,k \leqslant 20$.

$\texttt{Subtask 2 (5 pts)}$: For $5\%$ of the data, $0 \leqslant n,m,k \leqslant 500$.

$\texttt{Subtask 3 (15 pts)}$: For $15\%$ of the data, $0 \leqslant n,m,k \leqslant 4000$.

$\texttt{Subtask 4 (5 pts)}$: For $5\%$ of the data, $opt_i = 0$.

$\texttt{Subtask 5 (70 pts)}$: No special restrictions.

For $100\%$ of the data: $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$, and $opt_i \in \{0,\ 1,\ 2\}$.

Translated by ChatGPT 5