kinetic

Kinetic

== include(page="template/taskheader" task_id="kinetic") ==

Poveste şi cerinţă...

Se dau $N$ puncte care circula pe axa $Ox$. Pozitia celui de-al $i-lea$ punct la momentul de timp $t$ este dat de formula: $a{~i~} + b{~i~} * t$. Vi se mai dau deasemenea $M$ query-uri de forma $x y t$. Pentru fiecare vi se cere sa ziceti cate puncte sunt intre coordonatele $x$ si $y$ (inclusiv) la momentul de timp $t$.

h2. Date de intrare

Fişierul de intrare $kinetic.in$ ...

Fişierul de intrare $kinetic.in$ va contine pe prima linie $2$ numere naturale $N$, si $M$, numarul de puncte, respectiv numarul de query-uri.
Urmatoarele $N$ linii vor contine fiecare $2$ valori. Astfel cea de-a $i + 1$ linie va contine valorile $a{~i~}$, respectiv $b{~i~}$.
Urmatoarele $M$ linii vor contine fiecare $3$ valori, $x$, $y$ si $t$ reprezentand intervalul de pe axa $Ox$ la timpul $t$ pentru care se intreaba.

h2. Date de ieşire

În fişierul de ieşire $kinetic.out$ ...

În fişierul de ieşire $kinetic.out$ trebuie sa se gaseasca $M$ linii, cate una pentru fiecare query. Astfel cea de-a $i$-a linie din fisierul de iesire trebuie sa contina raspunsul pentru cel de-al $i$-lea query.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 500$
* $1 ≤ M ≤ 200.000$
* $-10.000 ≤ a{~i~}, b{~i~} ≤ 10.000$
* $-1.000.000.000 ≤ x, y ≤ 1.000.000.000$
* $0 ≤ t ≤ 1.000.000$

h2. Exemplu
table(example). |_. kinetic.in |_. kinetic.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 3 3
-9 -1
-2 -5
5 -8
91 -66 10
-73 38 4
86 23 7
|2
3
0

|
h3. Explicaţie

...

La momentul de timp $10$ punctele se vor afla la coordonatele $-9 + 10 * (-1) = -19$, $-2 + 10 * (-5) = -52$ si $5 + 10 * (-8) = -75$. Dintre acestea doar primele $2$ se afla intre $91$ si $-66$ pe axa $Ox$.

== include(page="template/taskfooter" task_id="kinetic") ==
 

== include(page="template/taskfooter" task_id="kinetic") ==