대회가 끝나고 난 뒤 빰빠빰

CEOI 2011 준비를 마치고 나니 파티를 열고 싶어졌다. 사실 파티보다 풍선을 부는 일이 더 하고 싶다. 바닥에 완전한 공 모양의 풍선 $n$개가 놓여 있다.

아직 바람을 넣지 않아 각 풍선의 반지름은 $0$에서 시작한다. $i$번째 풍선은 $x_i$ 좌표에 고정되어 있어 움직이거나 공중에 떠오르지 않는다. 풍선은 왼쪽에서 오른쪽 순서대로 하나씩 바람을 넣는다. 각 풍선은 자신의 최대 반지름 $r_i$에 도달하거나, 먼저 부풀린 다른 풍선과 맞닿는 순간까지 점점 커진다.

그림 1: 예제의 풍선을 모두 부풀린 모습.

모든 풍선의 최종 반지름을 구하여라.

첫째 줄에 풍선의 개수 $n$이 주어진다 ($1 \le n \le 200,000$).

이어지는 $n$개의 줄 중 $i$번째 줄에는 두 정수 $x_i$와 $r_i$가 공백으로 구분되어 주어진다. $x_i$는 풍선이 놓인 $x$좌표이며 ($0 \le x_i \le 10^9$), $r_i$는 그 풍선이 커질 수 있는 최대 반지름이다 ($1 \le r_i \le 10^9$). 풍선은 왼쪽에서 오른쪽 순서로 주어지며 $x$좌표는 엄격히 증가한다. 즉 $x_1 < x_2 < \dots < x_n$이다.

$n$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 풍선의 최종 반지름을 소수점 아래 셋째 자리까지 반올림하여 출력한다.