有两种货币:卵石和珠子。最初你有 $$$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$$$ 可以拥有的最大卵石数量。
输入
输入的第一行包含一个整数 $$$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$$$。
输出
输出 $$$n$$$ 数字 — 每天结束时卵石的最大数量。
如果您的答案的绝对或相对误差不超过 $$$10^{-6}$$$,则视为正确。
正式来说,让您的答案为 $$$a$$$,陪审团的答案为 $$$b$$$。当且仅当 $$$\frac{\left|a - b\right|}{\max(1, \left|b\right|)} \le 10^{-6}$$$ 时,您的答案才会被接受。
示例
输入 #1
3 2 6 0 2 3 4 2 3 0 6 4 2 10 2 3 10 1 10 10 33 1000
输出 #1
6 8 4 6 9.000000 10.33
注意
在下图中,您可以看到前两个测试用例的解决方案。每行都有每天的最佳行动顺序。
在第一个测试用例中,第一天的最佳策略是根本不执行任何操作,因为我们只能减少卵石的数量。第二天的最佳策略是首先用 $$$1$$$ 卵石交换 $$$2$$$ 珠子,这是正确的交换,因为 $$$1 \cdot 4 = 2 \cdot 2$$$,然后用 $$$2$$$ 珠子交换 $$$3$$$ 卵石。