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

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

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

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

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

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

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