Maximum Segment Length with Marker Constraints

Little X draws a number line and performs n operations. In each operation, he first adds a_i markers at position x_i on the number line. Then, he needs to choose a pair of integers \( (l, r) \) satisfying \(0 \le l \le r \le m\) such that the total number of markers in the interval \( [l, r] \) is at most \(k\) (i.e. \(\sum_{i=l}^{r} \text{markers}_i \le k\)). For each operation, you are required to output the maximum value of \(r - l\) among all valid pairs \( (l, r) \).

Note: The operations are cumulative. That is, the marker additions in one operation persist into the subsequent operations.

inputFormat

The first line contains three integers \(m\), \(n\), and \(k\), where \(m\) is the maximum position on the number line, \(n\) is the number of operations, and \(k\) is the marker limit for any segment.

Each of the next \(n\) lines contains two integers \(x_i\) and \(a_i\) indicating that \(a_i\) markers are added at position \(x_i\) during that operation.

outputFormat

Output \(n\) lines. The \(i\)-th line should contain a single integer representing the maximum value of \(r-l\) for the current state after the first \(i\) operations such that the total number of markers in the interval \( [l, r] \) does not exceed \(k\).

sample

5 3 3
2 3
4 1
0 1

5
3
2