Mirror Cupa SEPI Seniori | Barcode

Sătul de mâncat fripturi și salate, Raul a devenit light artist (artist de lumini). Pentru următorul său spectacol el are $N$ lumini așezate într-o linie, numerotate de la $1$ la $N$, care sunt inițial stinse. În continuare, la fiecare secundă, timp de $M$ secunde, el va alege o secvență continuă de lumini și le va schimba starea; adică luminile stinse se vor aprinde, iar luminile aprinse se vor stinge. Spectacolul se finalizează la o secundă după ultima schimbare.

Cerință

După încheierea spectacolului, el se întreabă, pentru $Q$ intervale de lumini, pentru câte secunde a fost fiecare interval complet aprins (adică toate luminile din interval sunt aprinse în același timp).

Date de intrare

Pe prima linie se află trei numere naturale $N$, $M$ și $Q$, reprezentând numărul de lumini, numărul de schimbări, respectiv numărul de intervale pentru care Raul vrea răspunsul la întrebare.

Pe următoarele $M$ linii se află câte două numere naturale $l$ și $r$, reprezentând, în ordine, capetele secvențelor schimbate.

Pe următoarele $Q$ linii se află câte două numere naturale $l$ și $r$, reprezentând intervalele de lumini pentru care Raul vrea să răspundă la întrebare.

Date de ieșire

Pe o singură linie, se vor afișa $Q$ numere naturale, separate prin câte un spațiu, reprezentând răspunsurile pentru cele $Q$ întrebări.

Restricții și precizări

• $1 \leq N, M, Q \leq 200 \ 000$;
• $1 \leq l_i, r_i \leq N$, pentru orice $1 \leq i \leq M$ în intervalele schimbate, respectiv $1 \leq i \leq Q$ în intervalele de interogare.

Exemplul 1

stdin

5 4 3
2 4
1 2
3 5
2 4
1 2
2 4
3 3

stdout

1 2 3

Explicație

Șirul va arăta, pe rând, astfel:

$t = 0: \quad \texttt{0 0 0 0 0}$
$t = 1: \quad \texttt{0 \textcolor{red}{1 1 1} 0}$
$t = 2: \quad \texttt{\textcolor{red}{1 0} 1 1 0}$
$t = 3: \quad \texttt{1 0 \textcolor{red}{0 0 1}}$
$t = 4: \quad \texttt{1 \textcolor{red}{1 1 1} 1}$

Se observă, pentru a treia interogare, că lumina $3$ este aprinsă timp de $3$ secunde.

Exemplul 2

stdin

7 7 7
1 5
3 7
2 6
3 4
1 5
2 4
3 6
1 2
3 5
4 6
2 4
4 6
1 3
2 3

stdout

2 3 1 2 1 1 2

Explicație

Șirul va arăta, pe rând, astfel:

$t = 0: \quad \texttt{0 0 0 0 0 0 0}$
$t = 1: \quad \texttt{\textcolor{red}{1 1 1 1 1} 0 0}$
$t = 2: \quad \texttt{1 1 \textcolor{red}{0 0 0 1 1}}$
$t = 3: \quad \texttt{1 \textcolor{red}{0 1 1 1 0} 1}$
$t = 4: \quad \texttt{1 0 \textcolor{red}{0 0} 1 0 1}$
$t = 5: \quad \texttt{\textcolor{red}{0 1 1 1 0} 0 1}$
$t = 6: \quad \texttt{0 \textcolor{red}{0 0 0} 0 0 1}$
$t = 7: \quad \texttt{0 0 \textcolor{red}{1 1 1 1} 1}$

Se observă, pentru prima interogare, că luminile $1$ și $2$ sunt simultan aprinse timp de $2$ secunde.