Dominoes

Pixar is preparing to premiere its next animated film, Elemental, at the 2023 Cannes Film Festival. One scene needs to be re-rendered. The scene has $n$ dominoes in a straight line. When one of them falls, it knocks over the dominoes after it in a chain. The festival is less than a month away, so Pixar asks you to write a program that computes the cost of re-rendering the scene for each choice of the initial domino.

To keep the calculation simple, treat each domino as a line segment with no width on the coordinate axis. The dominoes fall to the left. They are numbered from left to right, and domino $i$ has height $l_i$ and is located at $x_i$. The cost of re-rendering is the area of the moving part of the scene, which is the union of the quarter circles traced by the dominoes that fall. Falling areas may overlap, and any overlapped area is counted only once. The picture shows the fall when domino 5 is the initial domino.

The first line contains a positive integer $n$, the number of dominoes. Each of the next $n$ lines contains two integers $x_i$ and $l_i$, the location and the height of domino $i$. The dominoes are given from left to right, so $x_i < x_{i+1}$. It is guaranteed that $n \le 200000$ and $1 \le x_i, l_i \le 10^9$.

Output $n$ lines. The $i$-th line contains the cost of re-rendering the scene when domino $i$ is the initial falling domino. Every number must have an absolute or relative error of at most $10^{-6}$.