Proiectoare

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.

Cerinţă

Dându-se $Q$ intervale de forma $[X_i, Y_i]$ 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 $[X_i, Y_i]$ se va afișa valoarea $0$.

Date de intrare

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 $S_i, D_i$, 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 $X_i, Y_i$, separate printr-un spațiu, reprezentând intervalele pentru care se realizează verificările.

Date de ieșire

În fișierul text proiectoare.out se vor scrie $Q$ linii; pe linia $i \ (1 ≤ i ≤ Q)$ se va scrie un număr natural reprezentând lungimea intervalului obținut ca răspuns la verificarea efectuată pentru intervalul $[X_i, Y_i]$.

Restricții și precizări

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

Exemplu

proiectoare.in

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

proiectoare.out

4
2
1
2
0

Explicație

Pentru verificarea $[1,10]$ cel mai lung interval complet iluminat este $[4,8]$ cu lungimea $4$.

Pentru verificarea $[2,5]$ cele mai lungi intervale complet iluminate sunt $[2,4]$ și $[3,5]$, ambele au lungimea $2$.

Pentru verificarea $[3,4]$ cel mai lung interval complet iluminat este $[3,4]$ cu lungimea $1$.

Pentru verificarea $[6,8]$ cel mai lung interval complet iluminat este $[6,8]$ cu lungimea $2$.

Pentru verificarea $[8,9]$ se afișează valoarea $0$.