Zebra Prince’s Intellectual Quest

The Zebra Prince rules an endless grassland where a magical river flows and each point on the grassland is endowed with a certain memetic force corresponding to its distance from the river's source. Initially, you are given an array \(s\) of length \(k+1\) where \(s_i = 0\) for all \(0 \le i \le k\). Then, there are \(n\) intervals \( (l_i, r_i) \). For each such interval, for every integer \(i \in [l_i, r_i]\), set \(s_i = 1\) (indicating that a hunter camp has been established on that grassy spot).

Define the set \(S = \{ x \in \mathbb{Z} \mid 0 \le x \le k \ \text{and}\ s_x = 0 \}\), which represents the indices that are free of hunter camps.

After the initial setup, there will be \(m\) events. Each event is given as a triple \((opt_i, a_i, b_i)\) (with \(0 \le a_i \le b_i \le k\) and \(opt_i \in \{0, 1, 2\}\)). The events are processed in order and can be one of the following types:

• Query (opt = 0): For every integer day \(x\) in the interval \([a_i, b_i]\), the Zebra Prince wishes to dine on a camp-free spot. His "intellect" for day \(x\) is computed as \(x \oplus y\), where \(y\) is chosen from \(S\) such that \(x \oplus y\) is minimized. Formally, you must compute \[ t_i = \sum_{x=a_i}^{b_i} \min_{y \in S} (x \oplus y). \] If \(s_x = 0\) (i.e. \(x \in S\)), then \(x \oplus x = 0\) is the minimum.
• Update Type 1 (opt = 1): Set \(s_i = 1\) for all \(i \in [a_i, b_i]\). (Hunter camps are established in these positions.)
• Update Type 2 (opt = 2): Set \(s_i = 0\) for all \(i \in [a_i, b_i]\). (Hunter camps are removed from these positions.)

Note: All calculations involving \(\oplus\) (the bitwise XOR operator) and the summations should be carried out using standard integer arithmetic. It is guaranteed that the input events are such that when a query event (opt = 0) is performed, if there is no candidate \(y\) in \(S\) then you should consider the contribution for that day as 0.

This problem requires you to process interval updates and queries on an array, while dynamically maintaining the set \(S\) and computing a bitwise XOR based cost function.

inputFormat

The input is given as follows:

k n m
l_1 r_1
l_2 r_2
... 
l_n r_n
opt_1 a_1 b_1
opt_2 a_2 b_2
...
opt_m a_m b_m

Here, \(k\) (\(0 \le k\)) is the maximum index, \(n\) is the number of initial intervals where hunter camps are established, and \(m\) is the number of subsequent events. For the initial \(n\) intervals, each line contains two integers \(l_i\) and \(r_i\) (with \(0 \le l_i \le r_i \le k\)). For the following \(m\) events, each event is given as three integers: \(opt_i\) (which is 0, 1, or 2), and \(a_i, b_i\) (with \(0 \le a_i \le b_i \le k\)).

outputFormat

For each query event (where \(opt_i = 0\)), output a single line containing the integer \(t_i\) representing the minimum possible sum of the intellectual values over the days in the interval \([a_i, b_i]\).

sample

10 2 5
0 2
7 8
0 3 5
1 4 9
0 0 10
2 5 7
0 5 7

0
33
0