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ța

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.

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 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.

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 [Xi, Yi].

Restricții și precizări

• 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 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

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.