La intrarea unui mic ștrand dintr-o stațiune de băi termale, cu o jumătate de oră înaintea deschiderii, s-a format o coadă de $N$ oameni, indexați începând cu 1.
Datorită timpului îndelungat de așteptare, la fața locului s-au adunat $M$ distribuitori de pliante cu reclame. Fiecare distribuitor are un singur interval $[l, r]$ pe care acționează, oferind câte un pliant fiecărei persoane cu indicele $i$, unde $l \leq i \leq r$.
Definim gradul de irascibilitate al unei persoane ca fiind numărul de pliante pe care le primește. Urmărind să detensioneze situația, directorul vine și îi pune $Q$ întrebări lui Felix, programatorul companiei. Pentru fiecare întrebare, el îi dă lui Felix un număr $x$ și vrea să afle care este cel mai mare grad de irascibilitate (îl vom nota cu $g$) al unei persoane, astfel încât să existe minim $x$ persoane cu grad de irascibilitate mai mare decât $g$.
Se dau $N$, $M$, cele $M$ intervale de forma $[l, r]$ și cele $Q$ query-uri, fiecare cu câte o valoare $x$. Pentru fiecare query, se cere să se afle cel mai mare numar $g$, reprezentând gradul de irascibilitate al unei persoane din șir, astfel încat să existe minim $x$ persoane cu grad de irascibilitate mai mare decât $g$.

Date de intrare

Fișierul de intrare felix.in va conține pe prima linie două numere $N$ și $M$, $N$ reprezentând numărul de persoane, iar $M$ reprezentând numărul de intervale. Pe următoarele $M$ linii se află câte două numere, reprezentând capetele unui interval $[l, r]$. Pe următoarea linie, se află numarul $Q$, reprezentând numărul de interogări. Pe următoarele $Q$ linii, se află câte un număr $x$, cu sensul din enunț.

Date de ieșire

Fisierul de ieșire felix.out va conține $Q$ linii, fiecare cu câte un număr $q_i$, care reprezintă răspunsul la query-ul cu indicele $i$.

Restricții si precizări

• Dacă nu există soluție pentru un query, se va afișa $-1$ pe linia corespunzătoare
• $N \leq 1 \ 000 \ 000 \ 000$
• $Q \leq 100 \ 000$
• $M \leq 100 \ 000$
• $x \leq 1 \ 000 \ 000 \ 000$
• Notăm cu $L$ lungimea maximă a unui interval, $L \leq N$.
• Pentru teste în valoare de $15$ puncte $L$, $Q$, $M \leq 1 \ 000$, $N \leq 100 \ 000$.
• Pentru alte teste în valoare de $17$ puncte $Q$, $M \leq 1 \ 000$, $N \leq 1 \ 000 \ 000$.
• Pentru alte teste în valoare de $31$ puncte $Q$, $M \leq 100 \ 000$, $N \leq 1 \ 000 \ 000$.
• Pentru alte teste în valoare de $37$ de puncte, nu există restricții suplimentare.

Exemplul 1

felix.in

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

felix.out

3
0
2

Exemplul 2

felix.in

6 3
2 5
2 3
4 5
2
4
5

felix.out

0
-1

Explicații

Pentru primul exemplu, cele $7$ persoane au următoarele grade de irascibilitate, în ordine: $1 \ 2 \ 3 \ 4 \ 2 \ 1 \ 0$.
Pentru primul query, $x$ este $1$ și există o singură persoană care are grad mai mare decât $3$. Pentru al doilea query, $x$ este $5$. Există doar $4$ persoane cu grad mai mare decât $1$, dar $6$ persoane cu grad mai mare decât $0$. Astfel, răspunsul este $0$. Pentru al treilea query, $x$ este $2$ și există fix două persoane cu grad mai mare decât $24.

Pentru al doilea exemplu, cele $6$ persoane au următoarele grade de irascibilitate, în ordine: $0 \ 2 \ 2 \ 2 \ 2 \ 0$.
Pentru primul query, $x$ este $4$ și există $4$ persoane cu grad mai mare decât cel al persoanelor care au gradul $0$. Pentru al doilea query, $x$ este $5$ și nu există nicio persoană care să aibă grad de irascibilitate mai mic decât minim $5$ persoane.