Description

胖子和瘦子在一个山洞里行走，胖子在瘦子前面。每个人都有一支火把。

胖子的火把填满燃料后可以燃烧 $a_1$ 秒，在熄灭后需要花费 $b_1$ 秒填充燃料。

瘦子的火把填满燃料后可以燃烧 $a_2$ 秒，在熄灭后需要花费 $b_2$ 秒填充燃料。

每个人只能在自己的火把燃烧时前进，速度为 $1\operatorname{m/s}$。

因为胖子太胖，所以瘦子只能跟在胖子后面而不能超过胖子。

每一秒胖子先移动，之后瘦子再移动。

初始时两个人的火把都已经填满了燃料，瘦子在胖子后面 $1 \operatorname{m}$。

给定 $n$ 个询问，每次给一个正整数 $q_i$，表示查询第 $q_i$ 秒后，瘦子的移动距离。

接下来 $n$ 行，每行一个正整数 $q_i$，表示询问。

Input Format

本题包含多组测试数据

第一行一个正整数 $T$，表示数据组数。

对于每组数据：

Output Format

每组数据输出 $n$ 行，表示每个询问的答案，即第 $q_i$ 秒后瘦子的移动距离。

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

Hint

下面 $\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}$。