substantiv

-- Puteți să îi scrieți soțului meu că copiii au venit să mănânce?
-- Sigur, dar câți copii sunt?
-- 4, de ce?
-- Păi ca să știu câți "i" să pun.

Definim substantivul comun gigel cu gen masculin (un gigel, doi gigei), care reprezintă un copil de 7 ani, 4 luni și 16 zile numit Gigel.

În parc există exact $N$ gigei, mai exact $gigel_1, gigel_2, \dots, gigel_N$. Aceștia sunt cu mamele lor ($mama_1, mama_2, \dots, mama_N$). Fiecare $mama_i$ intenționează ca $gigel_i$ să stea în parc de la momentul $st_i$ la momentul $dr_i$.

Însă, mamele au un obicei foarte ciudat, neînțeles de nimeni. La fiecare moment $t$, dacă $t$ este prim și $gigel_i$ este în parc, $mama_i$ îl va mai lăsa încă un minut după (cu alte cuvinte, $dr_i$ crește cu $1$).

La fiecare moment $t$, efectul gigela are gravitate $x$, unde $x$ reprezintă numărul de gigei din parc în momentul $t$.

Lumea este o simulare de la momentul $1$ până la momentul $T$, iar tu ești un angajat al celor care o controlează (Gigelsoft). Cerința ta este să monitorizezi efectele gigela.

Cerință

Pentru a verifica dacă ai lucrat sau nu, compania Gigelsoft te întreabă, pentru anumite momente de timp, care a fost gravitatea maximă a unui efect gigela de la începutul simulării până la acel moment de timp.

Date de intrare

Pe prima linie a fișierului de intrare substantiv.in se găsesc trei numere naturale, $N$, $T$ și $Q$. Pe a următoarele $N$ linii se găsesc câte două numere naturale $st_i$ și $dr_i$, cu semnificația din enunț. Pe următoarea linie se găsesc $Q$ numere, reprezentând momentele de timp pentru care ești întrebat.

Date de ieșire

Pe cele $Q$ linii ale fișierului de ieșire substantiv.out se va găsi câte un număr natural, reprezentând răspunsurile la întrebări.

Restricții și precizări

• $1 \leq N \leq 200 \ 000$
• $1 \leq Q \leq 1 \ 000 \ 000$.
• Vom considera că $st_i$ și $dr_i$ sunt cele finale.
• $1 \leq st_i \leq dr_i \leq T \leq 1 \ 000 \ 000$
• $1 \leq t \leq T$, unde $t$ este valoarea dată la o întrebare.
• Notăm cu $\sum t$ suma $t$-urilor de la întrebări.

Exemplu

substantiv.in

5 30 3
2 6
5 10
3 8
12 14
3 12
4 18 12

substantiv.out

3
4
4

Explicație

Acestea sunt intervalele de timp în care gigeii vor sta în parc:

1. de la $2$ la $10$
2. de la $5$ la $14$
3. de la $3$ la $12$
4. de la $12$ la $15$
5. de la $3$ la $18$