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 oameni, indexați începând cu 1.
Datorită timpului îndelungat de așteptare, la fața locului s-au adunat distribuitori de pliante cu reclame. Fiecare distribuitor are un singur interval pe care acționează, oferind câte un pliant fiecărei persoane cu indicele , unde .
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 întrebări lui Felix, programatorul companiei. Pentru fiecare întrebare, el îi dă lui Felix un număr și vrea să afle care este cel mai mare grad de irascibilitate (îl vom nota cu ) al unei persoane, astfel încât să existe minim persoane cu grad de irascibilitate mai mare decât .
Se dau , , cele intervale de forma și cele query-uri, fiecare cu câte o valoare . Pentru fiecare query, se cere să se afle cel mai mare numar , reprezentând gradul de irascibilitate al unei persoane din șir, astfel încat să existe minim persoane cu grad de irascibilitate mai mare decât .
Date de intrare
Fișierul de intrare felix.in va conține pe prima linie două numere și , reprezentând numărul de persoane, iar reprezentând numărul de intervale. Pe următoarele linii se află câte două numere, reprezentând capetele unui interval . Pe următoarea linie, se află numarul , reprezentând numărul de interogări. Pe următoarele linii, se află câte un număr , cu sensul din enunț.
Date de ieșire
Fisierul de ieșire felix.out va conține linii, fiecare cu câte un număr , care reprezintă răspunsul la query-ul cu indicele .
Restricții si precizări
- Dacă nu există soluție pentru un query, se va afișa pe linia corespunzătoare
- Notăm cu lungimea maximă a unui interval, .
- Pentru teste în valoare de puncte , , , .
- Pentru alte teste în valoare de puncte , , .
- Pentru alte teste în valoare de puncte , , .
- Pentru alte teste în valoare de 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 persoane au următoarele grade de irascibilitate, în ordine: .
Pentru primul query, este și există o singură persoană care are grad mai mare decât . Pentru al doilea query, este . Există doar persoane cu grad mai mare decât , dar persoane cu grad mai mare decât . Astfel, răspunsul este . Pentru al treilea query, este și există fix două persoane cu grad mai mare decât $24.
Pentru al doilea exemplu, cele persoane au următoarele grade de irascibilitate, în ordine: .
Pentru primul query, este și există persoane cu grad mai mare decât cel al persoanelor care au gradul . Pentru al doilea query, este și nu există nicio persoană care să aibă grad de irascibilitate mai mic decât minim persoane.