CF1735F.Pebbles and Beads

There are two currencies: pebbles and beads. Initially you have $a$ pebbles, $b$ beads.

There are $n$ days, each day you can exchange one currency for another at some exchange rate.

On day $i$, you can exchange $-p_i \leq x \leq p_i$ pebbles for $-q_i \leq y \leq q_i$ beads or vice versa. It's allowed not to perform an exchange at all. Meanwhile, if you perform an exchange, the proportion $x \cdot q_i = -y \cdot p_i$ must be fulfilled. Fractional exchanges are allowed.

You can perform no more than one such exchange in one day. The numbers of pebbles and beads you have must always remain non-negative.

Please solve the following $n$ problems independently: for each day $i$, output the maximum number of pebbles that you can have at the end of day $i$ if you perform exchanges optimally.

有两种货币：鹅卵石（pebbles）和珠子（beads）。初始时你拥有 $a$ 个鹅卵石和 $b$ 个珠子。

共有 $n$ 天，每天你可以按某个汇率将一种货币兑换为另一种货币。

在第 $i$ 天，你可以用 $-p_i \leq x \leq p_i$ 个鹅卵石兑换 $-q_i \leq y \leq q_i$ 个珠子，或者反向兑换。允许当天不进行任何兑换。同时，若进行了兑换，则必须满足比例关系 $x \cdot q_i = -y \cdot p_i$。允许进行分数形式的兑换。

每天至多执行一次此类兑换。你的鹅卵石数量和珠子数量在任意时刻都必须保持为非负数。

请独立求解以下 $n$ 个问题：对每一天 $i$，输出在第 $i$ 天结束时，在最优兑换策略下你能拥有的鹅卵石的最大数量。

The first line of the input contains a single integer $t$ ($1 \le t \le 10^3$) — the number of test cases. The description of test cases follows.

The first line of each test case contains three integers $n$, $a$ and $b$ ($1 \le n \le 300\,000$, $0 \le a, b \le 10^9$) — the number of days and the initial number of pebbles and beads respectively.

The second line of each test case contains $n$ integers: $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le 10^9$).

The third line of each test case contains $n$ integers: $q_1, q_2, \ldots, q_n$ ($1 \le q_i \le 10^9$).

It is guaranteed that the sum of $n$ over all test cases doesn't exceed $300\,000$.

输入的第一行包含一个整数 $t$（$1 \le t \le 10^3$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含三个整数 $n$、$a$ 和 $b$（$1 \le n \le 300\,000$，$0 \le a, b \le 10^9$），分别表示天数、初始石子数量和初始珠子数量。

每个测试用例的第二行包含 $n$ 个整数：$p_1, p_2, \ldots, p_n$（$1 \le p_i \le 10^9$）。

每个测试用例的第三行包含 $n$ 个整数：$q_1, q_2, \ldots, q_n$（$1 \le q_i \le 10^9$）。

保证所有测试用例中 $n$ 的总和不超过 $300\,000$。

Output $n$ numbers — the maximum number of pebbles at the end of each day.

Your answer is considered correct if its absolute or relative error does not exceed $10^{-6}$.

Formally, let your answer be $a$, and the jury's answer be $b$. Your answer is accepted if and only if $\frac{\left|a - b\right|}{\max(1, \left|b\right|)} \le 10^{-6}$.

输出 $n$ 个数字——即每一天结束时石子数量的最大值。

若你的答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。

形式化地，设你的答案为 $a$，评测组的答案为 $b$。当且仅当 $\frac{\left|a - b\right|}{\max(1, \left|b\right|)} \le 10^{-6}$ 时，你的答案被接受。

In the image below you can see the solutions for the first two test cases. In each line there is an optimal sequence of actions for each day.

In the first test case, the optimal strategy for the first day is to do no action at all, as we can only decrease the number of pebbles. The optimal strategy for the second day is at first to exchange $1$ pebble for $2$ beads, which is a correct exchange, since $1 \cdot 4 = 2 \cdot 2$, and then to exchange $2$ beads for $3$ pebbles.

在下方图片中，您可以看到前两个测试用例的解法。每行对应每一天的最优操作序列。

在第一个测试用例中，第一天的最优策略是不进行任何操作，因为我们只能减少石子的数量。第二天的最优策略是：首先用 $1$ 颗石子交换 $2$ 颗珠子（该交换合法，因为 $1 \cdot 4 = 2 \cdot 2$），然后用 $2$ 颗珠子交换 $3$ 颗石子。