A. Episodes
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Кот Miston поставил на скачивание сериал «Котокоп» («Police Cat»). В сериале $$$n$$$ серий, $$$i$$$-я из которых сейчас скачивается со скоростью $$$v_i$$$, и браузер показывает, что $$$i$$$-я серия скачается ровно через $$$t_i$$$ минут, что не совсем верно.

Браузер рассчитывает время, исходя из предположения, что скорость скачивания $$$i$$$-й серии не изменится. Однако когда какая-то серия оказывается полностью скачанной, скорость скачивания других серий увеличивается (других причин для изменения скорости скачивания той или иной серии и правда нет). При этом соотношения скоростей скачивания еще не скачанных серий неизменны. Иными словами, если $$$v_i^t$$$ — скорость скачивания $$$i$$$-й серии в момент времени $$$t$$$, то для любых $$$i$$$ и $$$j$$$ верно, что при всех $$$t$$$, меньших момента окончания скачивания $$$i$$$-й или $$$j$$$-й серии, величина $$$\frac{v_i^t}{v_j^t}$$$ одинакова.

Никакой другой нагрузки на сеть, кроме скачивания $$$n$$$ серий, нет. То есть суммарная скорость скачивания $$$\sum\limits_{i=1}^n v_i^t$$$ постоянна (одинакова при любом $$$t$$$).

Определите для каждой серии реальный момент времени, в который завершится ее загрузка.

Входные данные

В первой строке ввода содержится целое число $$$n$$$ — количество серий в сериале ($$$1 \le n \le 3 \cdot 10^5$$$).

Каждая из следующих $$$n$$$ строк содержит два целых числа $$$v_i$$$ и $$$t_i$$$ — текущая скорость скачивания и предполагаемое браузером время скачивания $$$i$$$-й серии ($$$1 \le v_i, t_i \le 10^{18}$$$; $$$\sum\limits_{i=1}^n v_i \le 10^{18}$$$).

Выходные данные

Для каждой серии выведите настоящее время ее скачивания.

Ваш ответ будет засчитан, если его абсолютная или относительная ошибка не превосходит $$$10^{-6}$$$. Формально, пусть ваш ответ равен $$$a$$$, а ответ жюри равен $$$b$$$. Ваш ответ будет засчитан, если $$$\frac {|a - b|}{\max(1, b)} \le 10^{-6}$$$.

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

ПодзадачаБаллыОграничения Необходимые подзадачи Информация о проверке
0–примеры из условияполная
15$$$n \le 2$$$полная
25$$$n \le 3$$$0, 1первая ошибка
315$$$n, v_i, t_i \le 3000$$$0первая ошибка
420$$$n \le 3000$$$0 – 3первая ошибка
520$$$v_i = v_j$$$ для всех $$$i$$$, $$$j$$$первая ошибка
615$$$n \le 30\,000$$$0 – 4первая ошибка
75$$$t_i \le 10^{9}$$$ для всех $$$i$$$; $$$\sum\limits_{i=1}^n v_i \le 10^{9}$$$0, 3первая ошибка
815без дополнительных ограничений0 – 7первая ошибка
Примеры
Входные данные
2
2 4
3 5
Выходные данные
4
4.6
Входные данные
3
1 4
5 2
2 3
Выходные данные
2.5
2
2.375