28724번 - Сумасшедшие транспортные налоги 다국어

Артур Флек ведь когда-то был обычным человеком с обычными потребностями. Одной из них была покупка автомобиля.

Как известно, владение автомобилем подразумевает уплату транспортного налога, и Готэм в этом отношении не является исключением. Чтобы узнать стоимость транспортного налога на автомобиль, нужно знать мощность его двигателя в лошадиных силах. Далее по таблице налоговых ставок нужно выяснить налоговую ставку на данную мощность, а затем полученная ставка умножается на мощность.

Пример таблицы налоговых ставок:

Ставка, записанная в $i$-й строке, применяется для численных значений мощностей, которые строго больше мощности, указанной в той же строке, но при этом меньше либо равны мощности, указанной в следующей строке (если такая есть). В случае, если мощность строго больше максимальной мощности, указанной в таблице, то применяется максимальная ставка.

В процессе выбора автомобиля Артур перебрал множество вариантов и для каждого из них он хочет знать величину транспортного налога. Помогите ему!

В первой строке дано целое число $n$ --- число строк в таблице налоговых ставок ($1 \le n \le 100\,000$).

В следующих $n$ строках даны пары чисел $b_i$, $t_i$ --- мощность и соответствующая диапазону налоговая ставка из $i$-й строки ($0 \le b_i, t_i \le 10^9$). Гарантируется, что $b_1 = 0$, а также для любого $i$ верно: $b_i < b_{i + 1}$ и $t_i \le t_{i+1}$.

В следующей строке дано число $m$ --- число автомобилей, транспортный налог на которые хочет узнать Артур ($1 \le m \le 100\,000$).

В $j$-й из следующих $m$ строк дано целое число $q_j$ --- мощность $j$-го автомобиля ($1 \le q_j \le 10^9$).

Для каждого варианта автомобиля, интересующего Артура, выведите величину транспортного налога на него.