Description

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

A person goes shopping $n$ times. For each purchase, they carry $d_i$ coins of type $i$ and want to buy items worth an amount of $s$. For each purchase, how many payment methods are there?

Input Format

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

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

Output Format

For each purchase, output one line with a single integer representing the answer.

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

4
27

Hint

• Constraints
  For $100\%$ of the testdata, $1 \leq c_i, d_i, s \leq 10^5$, $1 \leq n \leq 1000$.

Translated by ChatGPT 5