Артур Флек ведь когда-то был обычным человеком с обычными потребностями. Одной из них была покупка автомобиля.
Как известно, владение автомобилем подразумевает уплату транспортного налога, и Готэм в этом отношении не является исключением. Чтобы узнать стоимость транспортного налога на автомобиль, нужно знать мощность его двигателя в лошадиных силах. Далее по таблице налоговых ставок нужно выяснить налоговую ставку на данную мощность, а затем полученная ставка умножается на мощность.
Пример таблицы налоговых ставок:
| Мощность (л.с.) | Ставка |
| 0 | 24 |
| 100 | 35 |
| 150 | 50 |
| 200 | 75 |
| 250 | 150 |
Ставка, записанная в $$$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 \lt 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$$$).
Для каждого варианта автомобиля, интересующего Артура, выведите величину транспортного налога на него.
5 0 24 100 35 150 50 200 75 250 150 5 107 143 152 170 150
3745 5005 7600 8500 5250
