O firma de curierat foloseste N drone. La momentul 0, drona i se afla la X_i metri de depozit si zboara direct spre el cu viteza constanta de Y_i metri pe secunda. Spunem ca drona a ajuns la depozit la secunda t daca in cele t secunde a parcurs cel putin X_i metri.
Dispecerul pune Q intrebari de forma: "cate drone au ajuns la depozit pana la secunda t ?". Raspundeti la fiecare intrebare.
- Date de intrare
- Pe prima linie se afla N. Pe fiecare dintre urmatoarele N linii se afla doua numere naturale X_i si Y_i (distanta si viteza dronei i). Pe linia urmatoare se afla Q, iar pe urmatoarele Q linii cate un numar natural t.
- Date de iesire
- Se afiseaza Q linii; linia k contine raspunsul la a k-a intrebare.
- Restrictii
- 1 <= N, Q <= 200 000 1 <= X_i <= 1 000 000 000 1 <= Y_i <= 1 000 1 <= t <= 1 000 000 000
Exemple
Exemplul 1
Intrare
5 90 3 15 4 100 7 30 1 50 10 5 5 30 4 15 1
Iesire
2 5 1 3 0
Exemplul 2
Intrare
3 10 5 20 10 7 7 3 1 2 3
Iesire
1 3 3