P9668 [ICPC 2022 Jinan R] Torch

胖子和瘦子在一个山洞里行走，胖子在瘦子前面。每个人都有一支火把。 胖子的火把填满燃料后可以燃烧 $a_1$ 秒，在熄灭后需要花费 $b_1$ 秒填充燃料。 瘦子的火把填满燃料后可以燃烧 $a_2$ 秒，在熄灭后需要花费 $b_2$ 秒填充燃料。 每个人只能在自己的火把燃烧时前进，速度为 $1\operatorname{m/s}$。 因为胖子太胖，所以瘦子只能跟在胖子后面而不能超过胖子。 每一秒胖子先移动，之后瘦子再移动。 初始时两个人的火把都已经填满了燃料，瘦子在胖子后面 $1 \operatorname{m}$。 给定 $n$ 个询问，每次给一个正整数 $q_i$，表示查询第 $q_i$ 秒后，瘦子的移动距离。 接下来 $n$ 行，每行一个正整数 $q_i$，表示询问。

**本题包含多组测试数据** 第一行一个正整数 $T$，表示数据组数。 对于每组数据：

每组数据输出 $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}$。