Задача №113133. D
Недавно Петин учитель рассказал ему об операции деления с остатком. Число p называется частным , а число q — остатком от деления x на y , если x = y · p + q , а также 0 ≤ q < y , и p и q целые. С вычислением частного у Пети проблем не возникает, а вот получение остатка дается ему с трудом. Но так как Петя — отличник, он решил поупражнятся в вычислении остатка.
Дома Петя нашел его любимую последовательность чисел a 1 , a 2 , ..., a n . Теперь Петя будет выбирать числа b 1 , b 2 , ..., b m и с каждым b i из них выполнять следующие операции:
- Делить с остатком b i на a 1 ,
- Получившийся остаток делить с остатком на a 2 ,
- Получившийся после второй операции остаток делить на a 3 , и так далее,
- ...
- Остаток от ( n - 1) -ого деления делить с остатком на a n .
Для того, чтобы проверять себя, Петя попросил вас написать программу, которая по заданным последовательностям a 1 , a 2 , ..., a n и b 1 , b 2 , ..., b m найдет для каждого b i остаток от последнего ( n -ого) деления. Помогите Пете!
В первой строке входных данных находится число n ( 1 ≤ n ≤ 10 5 ). Во второй строке находится последовательность a 1 , a 2 , ..., a n , записанная через пробелы ( 1 ≤ a i ≤ 10 9 ). Далее следует число m ( 1 ≤ m ≤ 10 5 ), а после него на четвертой строке — числа b 1 , b 2 , ..., b m , разделенные пробелами ( 0 ≤ b i ≤ 10 9 ). Все числа во входных данных целые.
Выведите m чисел — остатки от последней операции для каждого b i .
В примере b 3 = 27 . Последовательность действий, выполняемая Петей, будет следующая. Сначала разделим 27 на a 1 = 10 , получим в остатке 7. Далее разделим 7 на a 2 = 9 , получим в остатке 7. Разделим 7 на a 3 = 5 , получим в остатке 2. Разделим 2 на a 4 = 7 , получим в остатке 2, это и будет число, которое необходимо вывести.
4 10 9 5 7 5 14 8 27 11 25
4 3 2 1 0