402803: GYM100885 D Взять все остатки

Memory Limit:0 MB Time Limit:0 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

D. Взять все остаткиограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводrem.inвыводrem.out

Недавно Петин учитель рассказал ему об операции деления с остатком. Число p называется частным, а число q — остатком от деления x на y, если x = y·p + q, а также 0 ≤ q < y, и p и q целые. С вычислением частного у Пети проблем не возникает, а вот получение остатка дается ему с трудом. Но так как Петя — отличник, он решил поупражнятся в вычислении остатка.

Дома Петя нашел его любимую последовательность чисел a1, a2, ..., an. Теперь Петя будет выбирать числа b1, b2, ..., bm и с каждым bi из них выполнять следующие операции:

  1. Делить с остатком bi на a1,
  2. Получившийся остаток делить с остатком на a2,
  3. Получившийся после второй операции остаток делить на a3, и так далее,
  4. ...
  5. Остаток от (n - 1)-ого деления делить с остатком на an.

Для того, чтобы проверять себя, Петя попросил вас написать программу, которая по заданным последовательностям a1, a2, ..., an и b1, b2, ..., bm найдет для каждого bi остаток от последнего (n-ого) деления. Помогите Пете!

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

В первой строке входных данных находится число n (1 ≤ n ≤ 105). Во второй строке находится последовательность a1, a2, ..., an, записанная через пробелы (1 ≤ ai ≤ 109). Далее следует число m (1 ≤ m ≤ 105), а после него на четвертой строке — числа b1, b2, ..., bm, разделенные пробелами (0 ≤ bi ≤ 109). Все числа во входных данных целые.

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

Выведите m чисел — остатки от последней операции для каждого bi.

ПримерыВходные данные
4
10 9 5 7
5
14 8 27 11 25
Выходные данные
4 3 2 1 0 
Примечание

В примере b3 = 27. Последовательность действий, выполняемая Петей, будет следующая. Сначала разделим 27 на a1 = 10, получим в остатке 7. Далее разделим 7 на a2 = 9, получим в остатке 7. Разделим 7 на a3 = 5, получим в остатке 2. Разделим 2 на a4 = 7, получим в остатке 2, это и будет число, которое необходимо вывести.

加入题单

上一题 下一题 算法标签: