Sinulle annetaan $n$ suoraa $f_i(x) = a_i x + b_i$ ja $q$ kyselyä $x_i$. Palauta jokaiselle kyselylle $j$ pienin arvo $f_i(x_j)$.

Syöte

Ensimmäisellä rivillä on kaksi lukua $n$, $q$: suorien määrä ja kyselyiden määrä.

Toisella rivillä on $n$ lukua $a_1, \dots, a_n$.

Kolmannella rivillä on $n$ lukua $b_1, \dots, b_n$.

Neljännellä rivillä on $q$ lukua $x_1, \dots, x_q$.

Tuloste

Tulosta yhdellä rivillä $q$ lukua: pienimmät arvot $f_i(x_j)$ kaikilla $1 \leq j \leq q$.

Rajat

• $1 \leq n, q \leq 2 \cdot 10^5$
• $-10^9 \leq a_i, b_i, x_i \leq 10^9$

Esimerkki

Syöte:

4 6
2 -1 -1 1
20 15 9 12
-3 -1 2 -2 -5 -10

Tuloste:

9 10 7 10 7 0