[ICPC2022 Jinan R] Torch

## 题目描述 胖子和瘦子在一个山洞里行走，胖子在瘦子前面。每个人都有一支火把。 胖子的火把填满燃料后可以燃烧 $a_1$ 秒，在熄灭后需要花费 $b_1$ 秒填充燃料。 瘦子的火把填满燃料后可以燃烧 $a_2$ 秒，在熄灭后需要花费 $b_2$ 秒填充燃料。 每个人只能在自己的火把燃烧时前进，速度为 $1\operatorname{m/s}$。 因为胖子太胖，所以瘦子只能跟在胖子后面而不能超过胖子。 每一秒胖子先移动，之后瘦子再移动。 初始时两个人的火把都已经填满了燃料，瘦子在胖子后面 $1 \operatorname{m}$。 给定 $n$ 个询问，每次给一个正整数 $q_i$，表示查询第 $q_i$ 秒后，瘦子的移动距离。 ## 输入格式 **本题包含多组测试数据** 第一行一个正整数 $T$，表示数据组数。 对于每组数据： 第一行五个正整数 $a_1, b_1, a_2, b_2, n$，含义见题目描述。 接下来 $n$ 行，每行一个正整数 $q_i$，表示询问。 ## 输出格式 每组数据输出 $n$ 行，表示每个询问的答案，即第 $q_i$ 秒后瘦子的移动距离。 ## 数据范围 下面 $\sum n$ 表示所有数据的 $n$ 之和，$\sum a_1, \sum b_1, \sum a_2, \sum b_2$ 同理。 $1 \le T \le 10^5$，$1 \le a_1, b_1, a_2, b_2 \le 10^6$，$\sum a_1, \sum b_1, \sum a_2, \sum b_2, \sum n \le 10^6$，$1 \le q_i \le 10^{16}$。

Prof. Pang and Prof. Shou go to explore a cave together. Prof. Pang walks ahead of Prof. Shou. Each of them has a torch for illumination. The torches need fuel to burn. Prof. Pang's torch can burn for $a_1$ seconds once it has been refilled, and it takes $b_1$ seconds to refuel the torch after it burns out. Prof. Shou's torch can burn for $a_2$ seconds once it has been refilled, and it takes $b_2$ seconds to refuel the torch after it burns out. The person who is refueling the torch cannot walk simultaneously. For safety reasons, they cannot refuel the torch until the fuel runs out. Because Prof. Pang is too fat and the cave is too narrow, Prof. Shou cannot surpass Prof. Pang during the exploration, which means that Prof. Shou is at least 1 unit behind Prof. Pang. Each of them can walk forward a distance of 1 unit per second when his torch is burning. Every second, Prof. Pang moves first, then Prof. Shou does. In order to get to their destination earlier, they will move as long as they can walk forward. Now Prof. Shou has $n$ questions, and for the $i$-th question, he wants to know that at time $q_i$, how many units of the distance he has moved forward from the starting point? Prof. Shou starts 1 unit behind Prof. Pang. The initial time is 0. Both Prof. Pang and Prof. Shou refueled the torch before the initial time.

The first line contains one integer $T~(1\le T \le 10^5)$, the number of test cases. For each test case, the first line contains 5 integers $a_1, b_1, a_2, b_2, n~(1 \le a_1, b_1, a_2, b_2, n \le 10^6)$ denoting the time Prof. Pang's torch can burn, the time for Prof. Pang to refuel his torch, the time Prof. Shou's torch can burn, the time for Prof. Shou to refuel his torch, and the number of Prof. Shou's queries. Each of the next $n$ lines describes a query. Query $i$ is denoted by one integer $q_i~(1 \le q_i \le 10^{16})$. It is guaranteed that over all test cases, each of the following numbers is no more than $10^6$: - the sum of $a_1$, - the sum of $a_2$, - the sum of $b_1$, - the sum of $b_2$, - and the sum of $n$.

For each query, print one line containing the answer -- the number of units that Prof. Shou has walked forward from the starting point.

3
2 3 2 4 2
7
8
1 1 1 1 2
3
4
9 7 10 3 5
5
10
20
30
50

3
4
2
2
5
9
13
18
28