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

Условие

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

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

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

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

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

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

Вторая строка содержит n различных целых чисел a_i (1 = a₁ < a₂ < …  < a_n ≤ 10¹⁸).

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

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

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

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

Ограничения

1 ≤ n ≤ 200000

1 = a₁ < a₂ < …  < a_n ≤ 10¹⁸

1 ≤ q ≤ 200 000

1 ≤ b_i ≤ 10¹⁸

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

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

Замечание

• 2 будет выдано как 1 + 1,
• 8 будет выдано как 5 + 1 + 1 + 1,
• 49 будет выдано как 10 + 10 + 10 + 10 + 5 + 1 + 1 + 1 + 1.

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

4
1 5 10 50
3
2
8
50

2 2
8 4
49 9