Областная олимпиада по информатике, 2018 год, 10-11 класс

(Башни) У Алана есть $n$ башен, у каждой из которых есть параметр $a_i$ - числитель рук и параметр $b_i$ - знаменатель рук. В $q$ очень легких делах, которых он задумал, ему нужно определить руки у башен. Для этого, каждой башне он может сказать сделать целое количество рук - $[\frac{a_i}{b_i}]$ или дробное количество рук - $\frac{a_i}{b_i}$. Для $i$-го дела, которые он задумал, Алану необходимо суммарно ровно $x_i$ рук. Для каждого из этих дел Алан берет все $n$ башен, то есть суммарная \textit{рукость} всех башен должна равняться $x_i$. Помогите Алану найти количество способов сделать это, для каждого из $q$ легких дел.

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

В первой строке дается целое положительное число $n$ ($1 \le n \le 40$).
Во второй строке дается $n$ целых положительных чисел $a_1, a_2, .., a_n$ ($1 \le a_i \le 100000$)
В третьей строке дается $n$ целых положительных чисел $b_1, b_2, .., b_n$ ($1 \le b_i \le 100000$)
В следующей дается целое положительное число $q$ ($1 \le q \le 100000$) - количество запросов.
В следующих $q$ строках находится по одному целому числу $x$ - запросы из условия ($1 \le x \le 4000000$)

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

Выведите $q$ целых числе по одному в каждой строке - количество способов получить ровно $x_i$ целых рук.

Примеры:

1.Вход:

5
14 10 12 6 15
8 8 9 9 15
4
4
5
6
7

Ответ:

2
4
2
0

2.Вход:

3
6 2 8
8 8 4
2
2
3

Ответ:

2
2

Система оценки:

Задача содержит 100 тестов, каждая из которых весят 1 баллов.
Ограничения которые присутствуют в тестах:

• 20 теста: $(1 \le n \le 10, 1 \le q \le 5)$
  
• 31 тестов: $(1 \le n,q \le 20)$
  
• 49 тестов: $(1 \le n \le 40, 1 \le q \le 10^5)$
  

( Alan Amanov )