Description

X drew a number line. He will perform $n$ operations. In each operation, he first adds $a_i$ marks at position $x_i$ on the number line.

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

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

Input Format

The first line contains three integers, $n$, $m$, and $k$.

The next $n$ lines each contain two integers $x_i$ and $a_i$.

Output Format

Output $n$ lines, where the $i$-th line is the answer after the $i$-th operation.

If there is no valid pair $(l,r)$, output -1.

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

1
1
0
0
-1

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

15
11
11
7
6

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

100
93
83
77
77
77
68
44
40
26

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

100
100
100
94
80
59
56
53
50
39

Hint

[Sample Explanation #2]

After each operation, the chosen pairs are $(0,15),(4,15),(4,15),(8,15),(9,15)$.

[Constraints and Notes]

It is guaranteed that for test points $13\sim 16$, $x_i$ is generated randomly.

For test points $24,25$, the time limit is $3\text s$, and for all other test points, the time limit is $2\text s$.

For $100\%$ of the data, $1\le n\le 10^6$, $0\le m\le 10^9$, $0\le x_i\le m$, $0\le k\le 100$, and $1\le a_i\le 100$.

Note: Marks may be added multiple times at the same position on the number line.

$\text{O2}$ optimization is enabled automatically. It is guaranteed that the time and memory limits are both more than twice those of $\text{std}$ with $\text{O2}$ enabled.

Translated by ChatGPT 5