Прогрессивная задача
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Все мы любим прогресс! Автор этой задачи любит его настолько, что в этой задаче вам предстоит работать только с прогрессиями (при этом они возрастающие)!

Прогрессия — это последовательность чисел, заданная определённым правилом. Они бывают арифметическими и геометрическими.

Арифметическая прогрессия: $$$a_i = a_0 + d * i$$$.

Геометрическая прогрессия: $$$b_i = b_0 * q ^ i$$$.

Вам дано $$$k$$$ возрастающих последовательностей. Эти последовательности «сливаются»* в одну. Получается одна неубывающая последовательность $$$C$$$.

Вам необходимо ответить на $$$q$$$ запросов членов этой последовательности.

*Слияние — это объединение с сортировкой по неубыванию (то есть повторяющиеся элементы не удаляются). Работает аналогично слиянию в сортировке слиянием. См. примечание.

Входные данные

В первой строке вводится натуральное число $$$k$$$ $$$(1 \leq k \leq 10^5)$$$ — количество прогрессий.

В следующих $$$k$$$ строках вводятся по $$$3$$$ числа $$$t$$$ $$$x$$$ $$$y$$$ через пробел, где:

$$$t$$$ — тип прогрессии (1 арифметическая, 2 геометрическая)

$$$x$$$ — нулевой член прогрессии $$$(1 \leq x \leq 10^5)$$$

$$$y$$$ — коэффициент прогрессии ($$$d$$$ $$$(1 \leq d \leq 10^5)$$$ для арифметической, $$$q$$$ $$$(2 \leq q \leq 10)$$$ для геометрической)

В следующей строке вводится натуральное число $$$q$$$ $$$(1 \leq q \leq 2 \cdot 10^5)$$$ — количество запросов.

В следующих $$$q$$$ строках вводится по одному числу $$$i$$$ $$$(0 \leq i \leq 10^6)$$$ — член последовательности, который нужно вывести (в индексации с $$$0$$$).

Выходные данные

Выведите $$$q$$$ ответов (каждый на отдельной строке) — ответы на запросы.

Гарантируется, что все ответы не превосходят $$$10^{12}$$$.

Система оценки

Группы в данной задаче «склеиваются». Это означает, что за подгруппу начисляются баллы, если хотя бы одна из ваших посылок успешно проходит все её тесты.

Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи
$$$0$$$ | $$$0$$$ | Тесты из условия | —
$$$1$$$ | $$$25$$$ | $$$0 \leq i \leq 10$$$ | 0
$$$2$$$ | $$$25$$$ | $$$t = 2$$$ | —
$$$3$$$ | $$$50$$$ | — | 0, 1, 2

Пример

Входные данные

    21 1 12 1 270238196

Выходные данные

    1
    2
    2
    6
    1
    7
    4

Примечание

Пояснение сэмпла

Первая прогрессия имеет вид $$$a_i = 1 + i$$$: $$$1, 2, 3, 4, ...$$$

Вторая прогрессия имеет вид $$$b_i = 2^i$$$: $$$1, 2, 4, 8, ...$$$

Последовательность, полученная в результате «слияния»: $$$1, 1, 2, 2, 3, 4, 4, 5, 6, 7, 8, 8, 9, ...$$$