Problem Description

Little X draws a number axis and will perform \( n \) operations. Each operation involves adding \( a_i \) markers at position \( x_i \) on the number axis.

Then, he needs to choose a pair \((l, r)\), where \( l \) and \( r \) are integers, \( 0 \le l \le r \le m \), and the number of markers in the interval \([l, r]\) on the number axis is less than or equal to \( k \).

For each operation, you need to find the maximum value of \( r - l \) among the pairs \((l, r)\) that satisfy the condition.

Input Format

The first line contains three integers \( n \), \( m \), and \( k \).

The following \( n \) lines each contain two integers \( x_i \) and \( a_i \).

Output Format

Output \( n \) lines, each representing the answer after each operation.

If no pair \((l, r)\) satisfies the condition, output -1.

Sample Input and Output

Sample Input #1

5 4 0
2 1
3 1
0 1
1 1
4 1

Sample Output #1

1
1
0
0
-1

Sample Input #2

5 15 1
3 1
8 1
1 1
7 1
14 1

Sample Output #2

15
11
11
7
6

Sample Input #3

10 100 10
94 3
22 10
9 4
37 1
21 10
92 5
50 9
68 8
44 4
78 9

Sample Output #3

100
93
83
77
77
77
68
44
40
26

Sample Input #4

10 100 3
95 1
13 1
52 1
74 1
40 1
54 1
71 1
68 1
51 3
12 2

Sample Output #4

100
100
100
94
80
59
56
53
50
39

Notes

[Sample Explanation #2]

The pairs chosen after each operation are \((0, 15)\), \((4, 15)\), \((4, 15)\), \((8, 15)\), \((9, 15)\).

[Data Range and Constraints]

The \( x_i \) values for data points 13-16 are randomly constructed.

The time limit for data points 24, 25 is 3 seconds, and for other data points, it is 2 seconds.

For 100% of the data, it is guaranteed that \( 1 \le n \le 10^6 \), \( 0 \le m \le 10^9 \), \( 0 \le x_i \le m \), \( 0 \le k \le 100 \), \( 1 \le a_i \le 100 \).

Note: Multiple markers can be added at the same position on the number axis.

O2 optimization is automatically enabled, and the time and space limits are more than twice those of the standard solution with O2 optimization enabled.

见题面 Input 部分

见题面 Output 部分