409557: GYM103630 I Рудольф и подарочные наборы

I. Рудольф и подарочные наборыограничение по времени на тест2 секундыограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Перед новогодними праздниками Рудольф устроился в компанию, специализирующуюся на сборке новогодних подарков из конфет. Так как до Нового Года оставалось очень мало времени, в продаже были конфеты ровно четырёх видов, имеющие стоимости $$$C_1$$$, $$$C_2$$$, $$$C_3$$$, $$$C_4$$$ рубля за одну конфету.

Рудольфу поручили обработать $$$N$$$ заявок на сборку подарочных наборов. Каждая заявка имеет следующую структуру:

1. Четыре числа $$$L_1$$$, $$$L_2$$$, $$$L_3$$$, $$$L_4$$$ — максимальное количество конфет каждого вида, которое может быть в подарочном наборе.
2. Число $$$S$$$ — суммарная стоимость конфет, которую должен иметь подарочный набор.

Рудольф задумался, а сколько есть способов собрать каждый подарочный набор. Помогите ему ответить на этот вопрос.

Входные данные

Первая строка содержит целые числа $$$C_1$$$, $$$C_2$$$, $$$C_3$$$, $$$C_4$$$ ($$$1 \le C_1, C_2, C_3, C_4 \le 1000$$$) — стоимости конфет каждого вида.

Вторая строка содержит целое число $$$N$$$ ($$$1 \le N \le 2 \cdot 10^5$$$) — количество подарочных наборов.

Следующие $$$2 \cdot N$$$ строк содержат описания заявок на сборку подарочных наборов, имеющие формат, указанный в условии задачи. $$$L_1$$$, $$$L_2$$$, $$$L_3$$$, $$$L_4$$$ ($$$1 \le L_1, L_2, L_3, L_4 \le 10^9$$$) — максимальные количества конфет заданных видов в подарке, $$$S$$$ ($$$1 \le S \le 10^5$$$) — стоимость подарка.

Выходные данные

Выведите $$$N$$$ целых чисел — количества способов собрать каждый подарочный набор.

ПримерыВходные данные

5 1 2 3
2
1 1 1 1
7
5 5 5 5
6

Выходные данные

1
7

Входные данные

1 2 3 4
1
1 5 3 2
10

Выходные данные

8