AlgoLiga 2018

Bajtek pracuje w firmie informatycznej. Ostatnio, gdy ktoś kupował u nich płytę główną, spotkał go poważny problem. W kasie było mnóstwo pieniędzy każdego nominału, wręcz nieograniczona ilość. Już miał wydać klientowi resztę, gdy nagle uświadomił sobie, że nie wie jak to zrobić. Możliwości było tak dużo.. No właśnie, na tą chwilę nie ma nic bardziej istotnego niż odpowiedź na pytanie - na ile sposobów można to uczynić?

Weście

Wejście rozpoczyna się liczbą 1<=n<=10 oznaczającą ilość dostępnych nominałów. W następnej linii znajduje się n liczb (nie większych niż tysiąc) posortowanych rosnąco - są to kolejne dostępne nominały. W kolejnym wierszu podana jest liczba 1<=q<=10⁴ oznaczająca ilość zapytań. Każde zapytanie składa się z jednej liczby 1<=r<=10⁴.

Wyjście

Dla każdego zapytania należy wypisać w osobnej linii na ile możliwych sposobów Bajtek może wydać resztę r za pomocą dostępnych nominałów. Wynik nie przekracza 2⁶³ - 1.

Przykład

Wejście:
4
5 10 20 50
4
30
80
90
100

Wyjście:
6
31
39
49