F. Камушки и бусинки
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Есть две валюты: камушки и бусинки. Изначально у вас есть $$$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}$$$.

Пример
Входные данные
3
2 6 0
2 3
4 2
3 0 6
4 2 10
2 3 10
1 10 10
33
1000
Выходные данные
6
8
4
6
9.000000
10.33
Примечание

На изображении ниже можно видеть решения для первых двух наборов входных данных. В каждой строке указана оптимальная последовательность операций для каждого из дней.

В первом примере оптимальной стратегией для первого дня является не делать обмена вовсе, поскольку мы можем только уменьшить количество камушков. Для второго дня оптимальной стратегией является сначала обменять $$$1$$$ камушек на $$$2$$$ бусинки, что является корректным обменом, поскольку $$$1 \cdot 4 = 2 \cdot 2$$$, после чего обменять $$$2$$$ бусинки на $$$3$$$ камушка.