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$)
Yшінші жолда $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 )