Rezolvare PBinfo #1102

Pe o masă cad n bile săltăreţe. Fiecare este lăsată să cadă liber de la o înălţime h, diferită pentru fiecare bilă. Toate bilele cad simultan, cu o viteză constantă (1m/s) .

În momentul în care bila i atinge masa, tendinţa ei va fi să se ridice în aer până la înălţimea h - k, după care aceasta cade din nou. De fiecare dată când o bilă atinge masa, aceasta va tinde să urce la o înlăţime cu k mai mică decât cea la care a urcat anterior. Dupa multe sărituri, bilele pot obosi şi nu vor mai sări. Când bilele sar în sus, vor urca tot cu aceeaşi viteza constantă.

Dându-se h şi k pentru fiecare dintre cele n bile, să se răspundă la m întrebări de forma: La ce înălţime faţă de masă se va afla bila x în momentul t ?

Date de intrare

Fişierul de intrare bile2.in conţine pe prima linie 2 numere naturale n şi m. Pe următoarele n linii se află o pereche de numere, h şi k . Următoarele m linii vor conţine 2 numere naturale x şi t cu semnificaţiile de mai sus.

Date de ieşire

În fişierul de ieşire bile2.out se vor afişa m linii, răspunsurile la cele m întrebări.

Restricţii

• 1 ≤ n, m ≤ 100.000
• 1 ≤ h, k ≤ 1.000.000.000
• 1 ≤ t ≤ 2.000.000.000
• 0 < x ≤ n

Exemplu:

bile2.in

2 3
5 1
8 2
1 4
1 7
2 16

bile2.out

1
2
4

Explicaţie

Bila 1 cade de la înălţimea 5 timp de 4 secunde apoi se opreşte la înălţimea 1.

Bila 1 cade de la înălţimea 5 şi atinge pământul, iar în cele 2 secunde rămase ajunge la înălţimea 2.

Bila 2 cade de la înălţimea 8, atinge pământul şi apoi ajunge la noua sa înălţime maximă, 6, în 14 secunde. în cele 2 secunde rămase, bila apucă să coboare la înălţimea 4.