Есть две валюты: камушки и бусинки. Изначально у вас есть \(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\)-го дня, если совершать обмены оптимально.
Выходные данные
Выведите \(n\) чисел — максимальное количество камушков в конце каждого дня.
Ваш ответ будет считаться правильным, если его абсолютная или относительная ошибка не превосходит \(10^{-6}\).
Формально, пусть ваш ответ равен \(a\), а ответ жюри равен \(b\). Ваш ответ будет зачтен, если и только если \(\frac{\left|a - b\right|}{\max(1, \left|b\right|)} \le 10^{-6}\).
Примечание
На изображении ниже можно видеть решения для первых двух наборов входных данных. В каждой строке указана оптимальная последовательность операций для каждого из дней.
В первом примере оптимальной стратегией для первого дня является не делать обмена вовсе, поскольку мы можем только уменьшить количество камушков. Для второго дня оптимальной стратегией является сначала обменять \(1\) камушек на \(2\) бусинки, что является корректным обменом, поскольку \(1 \cdot 4 = 2 \cdot 2\), после чего обменять \(2\) бусинки на \(3\) камушка.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|