Coin Shopping

Problem Source

HAOI2008

Problem Description

There are $4$ kinds of coins, with face values $c_1, c_2, c_3, c_4$ respectively.

A person goes shopping $n$ times. For each purchase, he brings $d_i$ coins of the $i$-th kind and wants to buy goods worth $s$. For each purchase, how many ways are there to pay?

Input Format

The first line contains five integers, representing $c_1, c_2, c_3, c_4, n$.

The following $n$ lines each contain five integers describing one purchase, representing $d_1, d_2, d_3, d_4, s$.

For $100\%$ of the data, $1 \leq c_i, d_i, s \leq 10^5$ and $1 \leq n \leq 1000$.

Output Format

For each purchase, output one line containing an integer: the answer.

Sample Input

1 2 5 10 2
3 2 3 1 10
1000 2 2 2 900

Sample Output

4
27