Задача 7. Банкомат

Автор:Центральная предметно-методическая комиссия   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Ведётся разработка универсального банкомата, который сможет работать с любой денежной системой. Пусть в денежной системе некоторой страны используются n типов купюр, номиналы которых равны a1, a2, …, an. При этом все номиналы различны и перечислены в порядке возрастания: если i ≥ 2, то ai − 1 < ai, а также a1 = 1.

Банкомат использует следующий жадный алгоритм для выдачи купюр. Пусть клиент запросил у банкомата сумму c. Изначально есть пустой набор выдаваемых купюр. На каждом шаге алгоритм добавляет в набор купюру максимально возможного номинала так, чтобы сумма номиналов купюр в наборе не превышала c. Когда сумма номиналов купюр в наборе стала равна c, алгоритм останавливается. Отметим, что, поскольку существует купюра с номиналом a1 = 1, алгоритм всегда заканчивает работу за конечное число шагов.

Чтобы оценить эффективность данного алгоритма, требуется выяснить, какое максимальное число купюр может потребоваться выдать за один раз, если максимальная сумма, которую можно запросить, равна b. Поскольку максимальная сумма может зависеть от категории обслуживания клиента, необходимо ответить на q запросов для сумм b1, b2, …, bq.

Требуется написать программу, которая по списку номиналов купюр денежной системы и максимальной сумме, которую можно запросить, определяет сумму, которую необходимо запросить в банкомате, чтобы получить максимальное число купюр, и искомое число купюр.

Формат входных данных

Первая строка содержит целое число n — количество номиналов купюр (1 ≤ n ≤ 200 000).

Вторая строка содержит n различных целых чисел ai (1 = a1 < a2 < … < an ≤ 1018).

Третья строка содержит целое число q — количество запросов (1 ≤ q ≤ 200 000).

Следующие q строк содержат по одному целому числу bi (1 ≤ bi ≤ 1018).

Формат выходных данных

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

Ограничения

1 ≤ n ≤ 200000

1 = a1 < a2 < … < an ≤ 1018

1 ≤ q ≤ 200 000

1 ≤ bi ≤ 1018

Система оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Подзадача Баллы Ограничения Необходимые подзадачи Информация о проверке
113n ≤ 500, q ≤ 5, ai ≤ 500, bi ≤ 500первая ошибка
218n = 60, q ≤ 5, ai = 2i1первая ошибка
320 q ≤ 5, bi ≤ 2 ⋅ 1051первая ошибка
421q ≤ 51,2,3первая ошибка
5281,2,3,4первая ошибка

Замечание

Примеры тестов

Стандартный вход Стандартный выход
1
4
1 5 10 50
3
2
8
50
2 2
8 4
49 9

0.108s 0.024s 13