A. Episodes
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Cat Miston started downloading the series "Police Cat". The series consists of $$$n$$$ episodes, where the $$$i$$$-th episode is currently being downloaded at a speed of $$$v_i$$$ and the browser indicates that the $$$i$$$-th episode will be downloaded exactly in $$$t_i$$$ minutes, which is not entirely true.

The browser calculates the time based on the assumption that the download speed of the $$$i$$$-th episode will not change. However, when a certain episode is completely downloaded, the download speed of other episodes increases (there are no other reasons for changes in the download speed of any episode). At the same time, the ratios of download speeds of the remaining episodes remain unchanged. In other words, if $$$v_i^t$$$ is the download speed of the $$$i$$$-th episode at time $$$t$$$, then for any $$$i$$$ and $$$j$$$ it holds that for all $$$t$$$ less than the moment of download completion of the $$$i$$$-th or $$$j$$$-th episode the value of $$$\frac{v_i^t}{v_j^t}$$$ is the same.

There is no other network load besides downloading the $$$n$$$ episodes. In other words, the total download speed $$$\sum\limits_{i=1}^n v_i^t$$$ is constant (the same at any moment $$$t$$$).

Determine the actual time at which each episode will be fully downloaded.

Input

The first line of input contains an integer $$$n$$$ — the number of episodes in the series ($$$1 \le n \le 3 \cdot 10^5$$$).

Each of the following $$$n$$$ lines contains two integers $$$v_i$$$ and $$$t_i$$$ — the current download speed and the download time assumed by the browser for the $$$i$$$-th episode ($$$1 \le v_i, t_i \le 10^{18}$$$; $$$\sum\limits_{i=1}^n v_i \le 10^{18}$$$).

Output

For each episode output the actual time it will take to download it.

Your answer will be accepted 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 will be accepted if $$$\frac {|a - b|}{\max(1, b)} \le 10^{-6}$$$.

Scoring

Points for each subtask are awarded only if all tests for that subtask and the necessary subtasks are successfully passed.

SubtaskPointsConstraints Required subtasks Feedback policy
0–examplesfull
15$$$n \le 2$$$full
25$$$n \le 3$$$0, 1first error
315$$$n, v_i, t_i \le 3000$$$0first error
420$$$n \le 3000$$$0 – 3first error
520$$$v_i = v_j$$$ for all $$$i$$$, $$$j$$$first error
615$$$n \le 30\,000$$$0 – 4first error
75$$$t_i \le 10^{9}$$$ for all $$$i$$$; $$$\sum\limits_{i=1}^n v_i \le 10^{9}$$$0, 3first error
815no additional constraints0 – 7first error
Examples
Input
2
2 4
3 5
Output
4
4.6
Input
3
1 4
5 2
2 3
Output
2.5
2
2.375