Bessie's Hay Consumption

Bessie the cow eats one haybale each day at dinner if at least one haybale is available in the barn. In the morning of some days, Farmer John delivers a certain number of haybales. On day \(d_i\), he delivers \(b_i\) haybales. Initially, the barn is empty.

The process each day is as follows:

1. In the morning, if the day has a scheduled delivery, the corresponding haybales are added to the barn.
2. At dinner, if there is at least one haybale available in the barn, Bessie eats exactly one haybale.

You will be given \(U\) updates. Each update sets the number of haybales delivered on day \(d\) to \(b\) (i.e. any previous delivery on day \(d\) is overwritten). After each update, simulate the process from the beginning (with the current deliveries) and output the sum of all days on which Bessie eats a haybale modulo \(10^9+7\).

Note: The time limit for this problem is 6 seconds, three times the default. The memory limit is 512 MB, twice the default.

Hint: Since \(d\) can be as large as \(10^{14}\) and there can be up to \(10^5\) updates, a day‐by‐day simulation is too slow. Instead, process only the days on which deliveries occur and use arithmetic‐series formulas to accumulate the sum for intervals when Bessie consumes haybales continuously.

The arithmetic sum from \(A\) to \(A+L-1\) is given by \[ S = L \times A + \frac{L(L-1)}{2}. \]

inputFormat

The first line contains a single integer \(U\) \((1 \le U \le 10^5)\), the number of updates.

Each of the next \(U\) lines contains two space‐separated integers \(d\) and \(b\) \((1 \le d \le 10^{14},\ 0 \le b \le 10^9)\). Each update sets the hay delivery on day \(d\) to be \(b\) haybales.

outputFormat

After each update, output a single integer on its own line: the sum of all days on which Bessie eats a haybale, modulo \(10^9+7\).

sample

1
5 3

18