Submerging Levels

Farmer John is building an artificial lake to cool his cows during the oppressively hot summer days. The lake model consists of N contiguous platforms arranged from left to right (indexed 1..N). Each platform i is characterized by its width \(W_{i}\) and a unique height \(H_{i}\). At sunrise, water is poured at a rate of 1 square unit per minute into the platform with the lowest height. The water falls directly and, upon meeting a platform top (or previously poured water), instantly flows and equalizes across the entire connected region (basin) bordered by two infinitely tall barriers at the left and right ends.

As water is poured, its level, \(L\), increases piecewise linearly. When the water level above a platform reaches at least 1 unit above its top (i.e. when \(L \ge H_{i}+1\)), that platform is considered submerged. Note that as water fills the lake, new adjacent platforms join the basin once \(L\) becomes high enough to overcome their top elevation, causing an instantaneous increase in the overall basin area. In each phase, the water level increases according to the formula:

\( T = T_{0} + A \times (L - L_{0}) \)

where \(A\) is the current basin area, \(L_{0}\) is the water level at time \(T_{0}\), and \(L\) is the water level later. Using this model, your task is to determine the time at which each platform becomes submerged (i.e. the first time when the water is at least 1 unit over its top).

inputFormat

The first line contains an integer \(N\) (1 ≤ \(N\) ≤ 100,000). The following \(N\) lines each contain two integers \(W_{i}\) (1 ≤ \(W_{i}\) ≤ 1,000) and \(H_{i}\) (1 ≤ \(H_{i}\) ≤ 1,000,000), which represent the width and elevation of platform \(i\) in left-to-right order.

outputFormat

Output \(N\) lines, where the \(i\)-th line contains a single integer representing the time (in minutes) at which platform \(i\) becomes submerged. (Note: the answer may exceed 32-bit limits.)

sample

3
1 2
2 1
1 3

2
6
10