vmin

Vmin

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

Poveste şi cerinţă...

Se dau $N$ functii liniare de forma $AxT+B$. Sa se determine pentru $M$ query-uri, care este functia de valoare minima la un moment oarecare $T$. Query-urile se dau in ordine crescatoare dupa T.

h2. Date de intrare

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

Fişierul de intrare $vmin.in$ va contine pe prima linie numarul natural $N$. Pe urmatoarele $N$ linii se vor gasi $N$ perechi de numere intregi, reprezentand valorile $A$ si $B$ pentru fiecare functie. Pe linia $N+2$ se gaseste numarul $M$, de query-uri. Pe linia $N+3$ se vor gasi $M$ elemente, reprezentand momentele de timp pentru care trebuie sa determinam functia de valoare minima.

h2. Date de ieşire

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

În fişierul de ieşire $vmin.out$ se vor gasi pe o singura linie $M$ valori, reprezentand raspunsurile la cele $M$ query-uri. Raspunsul la un query este reprezentat de indicele functiei de valoare minima la acel moment.

h2. Restricţii

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

* $1 ≤ N ≤ 100 000$
* $1 ≤ M ≤ 1 000 000$
* $-10^9^ ≤ A,B ≤ 10^9^$

h2. Exemplu