Pang 教授和 Shou 教授一起去探索一个洞穴。Pang 教授走在 Shou 教授前面。

他们每个人都有一盏用于照明的火把。火把需要燃料才能燃烧。Pang 教授的火把加满燃料后可以燃烧 $a_1$ 秒，火把熄灭后重新加满燃料需要 $b_1$ 秒。Shou 教授的火把加满燃料后可以燃烧 $a_2$ 秒，火把熄灭后重新加满燃料需要 $b_2$ 秒。正在给火把加燃料的人不能同时行走。出于安全考虑，他们不能在燃料耗尽前给火把加燃料。

由于 Pang 教授太胖且洞穴太窄，在探索过程中 Shou 教授不能超过 Pang 教授，这意味着 Shou 教授始终在 Pang 教授身后至少 1 个单位距离处。

当火把燃烧时，他们每个人每秒可以向前走 1 个单位距离。每一秒，Pang 教授先移动，然后 Shou 教授移动。为了能更早到达目的地，只要能向前走，他们就会移动。

现在 Shou 教授有 $n$ 个问题，对于第 $i$ 个问题，他想知道在时间 $q_i$ 时，他从起点向前走了多少个单位距离？Shou 教授从距离 Pang 教授 1 个单位的位置开始。初始时间为 0。Pang 教授和 Shou 教授都在初始时间之前加满了火把。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试用例的数量。

对于每个测试用例，第一行包含 5 个整数 $a_1, b_1, a_2, b_2, n$ ($1 \le a_1, b_1, a_2, b_2, n \le 10^6$)，分别表示 Pang 教授火把的燃烧时间、Pang 教授加燃料的时间、Shou 教授火把的燃烧时间、Shou 教授加燃料的时间，以及 Shou 教授的查询次数。接下来的 $n$ 行每行描述一个查询。第 $i$ 个查询由一个整数 $q_i$ ($1 \le q_i \le 10^{16}$) 表示。

保证在所有测试用例中，以下各项之和均不超过 $10^6$： $a_1$ 的总和， $a_2$ 的总和， $b_1$ 的总和， $b_2$ 的总和， * $n$ 的总和。

输出格式

对于每个查询，输出一行，包含答案——即 Shou 教授从起点向前行进的单位距离数。

样例

输入 1

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

输出 1

3
4
2
2
5
9
13
18
28