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

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

Дома Петя нашел его любимую последовательность чисел a₁, a₂, ..., a_n. Теперь Петя будет выбирать числа b₁, b₂, ..., b_m и с каждым b_i из них выполнять следующие операции:

1. Делить с остатком b_i на a₁,
2. Получившийся остаток делить с остатком на a₂,
3. Получившийся после второй операции остаток делить на a₃, и так далее,
4. ...
5. Остаток от (n - 1)-ого деления делить с остатком на a_n.

Для того, чтобы проверять себя, Петя попросил вас написать программу, которая по заданным последовательностям a₁, a₂, ..., a_n и b₁, b₂, ..., b_m найдет для каждого b_i остаток от последнего (n-ого) деления. Помогите Пете!

В первой строке входных данных находится число n (1 ≤ n ≤ 10⁵). Во второй строке находится последовательность a₁, a₂, ..., a_n, записанная через пробелы (1 ≤ a_i ≤ 10⁹). Далее следует число m (1 ≤ m ≤ 10⁵), а после него на четвертой строке — числа b₁, b₂, ..., b_m, разделенные пробелами (0 ≤ b_i ≤ 10⁹). Все числа во входных данных целые.

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

4
10 9 5 7
5
14 8 27 11 25

4 3 2 1 0 

В примере b₃ = 27. Последовательность действий, выполняемая Петей, будет следующая. Сначала разделим 27 на a₁ = 10, получим в остатке 7. Далее разделим 7 на a₂ = 9, получим в остатке 7. Разделим 7 на a₃ = 5, получим в остатке 2. Разделим 2 на a₄ = 7, получим в остатке 2, это и будет число, которое необходимо вывести.