G. HDZ's Legendary Problem
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

This is a classical game of hero versus monsters.

A monster's attributes consist of base attributes and enhancement points.

The base attributes are:

  • Attack: $$$a$$$
  • Defense: $$$d$$$
  • Health: $$$h$$$
  • Speed: $$$s$$$

The monster has $$$n$$$ enhancement points that can be freely distributed among the four attributes $$$a,d,h,s$$$. Each enhancement point increases exactly one attribute by $$$1$$$, and the total number of enhancement points assigned must be exactly $$$n$$$.

The hero has fixed attributes:

  • Attack: $$$A$$$
  • Defense: $$$D$$$
  • Health: $$$H$$$
  • Speed: $$$S$$$

The battle proceeds in rounds. In each round, both sides attack each other once simultaneously.

The damage dealt from one side to the other is given by $$$$$$ \text{damage} = \max\left( \left\lceil \frac{\text{own speed}}{\text{opponent speed}} \right\rceil \times \text{own attack} - \text{opponent defense}, \; 1 \right). $$$$$$

The battle continues until the health of at least one side becomes less than or equal to $$$0$$$.

  • If both sides' healths become $$$\le 0$$$ in the same round, the result is a draw.
  • Otherwise, the side whose health becomes $$$\le 0$$$ first loses, and the other side wins.

You are given $$$q$$$ independent queries. For each query, the hero's attributes $$$A,D,H,S$$$ are given.

For each query, consider all possible monsters, i.e. all possible ways to distribute the $$$n$$$ enhancement points among the monster's base attributes $$$a,d,h,s$$$. The hero will fight each of these monsters. Each of the battles is independent.

For each query, let the number of battles the hero wins and loses be $$$w$$$ and $$$l$$$, respectively. Compute $$$w-l$$$.

Input

The first line of each test contains $$$5$$$ integers $$$a$$$, $$$d$$$, $$$h$$$, $$$s$$$, and $$$n$$$ ($$$1 \le a,h,s \le 200$$$, $$$0 \le d,n \le 200$$$), representing the base attributes of the monster and the number of enhancement points.

The following line contains an integer $$$q$$$ ($$$1 \le q \le 10^5$$$), representing the number of queries.

Each of the next $$$q$$$ lines contains $$$4$$$ integers $$$A$$$, $$$D$$$, $$$H$$$, and $$$S$$$ ($$$1 \le A,H,S \le 200$$$, $$$0 \le D \le 200$$$), representing the attributes of the hero.

Output

For each query, output $$$w-l$$$.

Examples
Input
1 1 1 1 2
3
2 2 2 2
1 1 1 1
3 3 3 3
Output
9
-4
10
Input
10 2 9 5 10
5
1 1 1 1
10 12 8 10
19 34 78 1
10 10 10 10
100 100 100 100
Output
-286
215
219
214
286
Note

In the first sample test, the monsters that the hero is going to fight are $$$(3,1,1,1)$$$, $$$(1,3,1,1)$$$, $$$(1,1,3,1)$$$, $$$(1,1,1,3)$$$, $$$(2,2,1,1)$$$, $$$(2,1,2,1)$$$, $$$(2,1,1,2)$$$, $$$(1,2,2,1)$$$, $$$(1,2,1,2)$$$, $$$(1,1,2,2)$$$.