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