Primăria a montat, pe faleza din Mamaia, $N$ proiectoare aşezate liniar, pentru fiecare cunoscându-se zona de faleză pe care o luminează, sub forma unui interval $[s,d]$, unde $s$ şi $d (s<d)$ sunt numere naturale reprezentând distanţele faţă de punctul unde începe faleza. Pentru a verifica eficienţa iluminării falezei, tehnicienii primăriei vor să determine intervalul de faleză de lungime maximă, iluminat de cel mult $K$ proiectoare, conţinut într-un interval $[X,Y]$ precizat. Pentru a fi siguri de corectitudinea rezultatelor obţinute, tehnicienii realizează $Q$ astfel de verificări.

Un interval se numeste iluminat de maxim $K$ proiectoare daca este inclus in reuniunea a $K$ sau mai putine proiectoare.
 

h2. Cerinţă
Dându-se $Q$ intervale de forma $[Xi,Yi]$ determinaţi, pentru fiecare dintre acestea, câte un interval de lungime maximă iluminat de cel mult $K$ proiectoare. Dacă nici un proiector nu iluminează vreo porţiune din intervalul $[Xi,Yi]$ se va afişa valoarea $0$.

Datele de intrare se citesc din fişierul text $proiectoare.in$, care are structura următoare:

{*} pe prima linie se află valorile naturale $N, Q, K$, separate prin câte un spaţiu, cu semnificaţia din enunţ;
{*} pe următoarele $N$ linii se află câte o pereche de valori naturale $Si, Di$, separate printr-un spaţiu, reprezentând intervalele iluminate de fiecare proiector;
{*} pe următoarele $Q$ linii se află câte o pereche de valori naturale $Xi,Yi$, separate printr-un spaţiu, reprezentând intervalele pentru care se realizează verificările.

* pe prima linie se află valorile naturale $N, Q, K$, separate prin câte un spaţiu, cu semnificaţia din enunţ;
* pe următoarele $N$ linii se află câte o pereche de valori naturale $Si, Di$, separate printr-un spaţiu, reprezentând intervalele iluminate de fiecare proiector;
* pe următoarele $Q$ linii se află câte o pereche de valori naturale $Xi,Yi$, separate printr-un spaţiu, reprezentând intervalele pentru care se realizează verificările.

h2. Date de ieşire

* $0 ≤ S < D ≤ 1 000 000 000$
* $1 ≤ K ≤ N ≤ 100 000$
* $1 ≤ Q ≤ 100 000$

* Pentru teste în valoare de $11$ puncte, $K=1$  şi $n ≤ 2000$ şi $Q ≤ 2000$

* Pentru teste în valoare de $11$ puncte, $K = 1$  şi $n ≤ 2000$ şi $Q ≤ 2000$

* Pentru teste în valoare de alte $38$ puncte, $K = 1$
* Pentru teste în valoare de alte $21$ puncte, $K = 2$
* Pentru teste în valoare de alte $10$ puncte, $K <= 30$