도미노

Pixar는 2023년 칸 영화제에서 신작 애니메이션 Elemental을 공개할 예정이다. 그런데 장면 하나를 다시 렌더링해야 한다. 이 장면에는 일직선으로 놓인 도미노 $n$개가 있고, 그중 하나가 쓰러지면 뒤의 도미노들이 연쇄적으로 쓰러진다. 영화제까지 한 달이 채 남지 않았으므로, Pixar는 시작 도미노를 고를 때마다 장면을 다시 렌더링하는 비용을 계산하는 프로그램을 요청했다.

계산을 단순하게 하기 위해 도미노를 좌표축 위의 폭이 없는 선분으로 본다. 도미노는 왼쪽으로 쓰러진다. 도미노는 왼쪽에서 오른쪽으로 번호가 매겨져 있으며, 도미노 $i$의 높이는 $l_i$이고 위치는 $x_i$이다. 렌더링 비용은 움직이는 부분의 넓이, 즉 쓰러지는 도미노들이 그리는 사분원의 합집합 넓이이다. 쓰러지는 영역끼리 겹칠 수 있으며, 겹치는 부분은 한 번만 계산한다. 그림은 5번 도미노를 시작 도미노로 골랐을 때 쓰러지는 모습을 보여 준다.

첫 줄에 양의 정수 $n$이 주어진다. 다음 $n$개의 줄에는 각각 정수 $x_i$와 $l_i$가 주어진다. 도미노는 왼쪽에서 오른쪽 순서로 주어지며, 즉 $x_i < x_{i+1}$이다. 제약 조건은 $n \le 200000$, $1 \le x_i, l_i \le 10^9$이다.

$n$개의 줄을 출력한다. $i$번째 줄에는 $i$번 도미노를 시작 도미노로 골랐을 때의 렌더링 비용을 출력한다. 모든 수는 절대 오차 또는 상대 오차가 $10^{-6}$ 이하여야 한다.