「EZEC-2」数轴

小 X 画了一条数轴，他将进行 $n$ 次操作，每次操作他会先在数轴上的 $x_i$ 位置上增添 $a_i$ 个标记。 然后他需要选择二元组 $(l,r)$，满足 $l,r$ 为整数， $0\le l\le r \le m$，且在数轴上的区间 $[l,r]$ 上的标记的个数**小于等于** $k$。 对于每次操作，你需要求出满足条件的二元组 $(l,r)$ 中 $r-l$ 的最大值。

第一行，三个整数，$n,m$ 和 $k$。 下面 $n$ 行，每行两个整数 $x_i$ 和 $a_i$。

共 $n$ 行，表示每次操作后的答案。 若找不到符合条件的二元组 $(l,r)$，输出 `-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

**【样例解释 #2】** 每次操作后选择的二元组分别是 $(0,15),(4,15),(4,15),(8,15),(9,15)$。 --- **【数据范围与约定】** | 数据点编号 | $n=$ | $m=$ | $k=$ | | :----------: | :----------: | :----------: | :----------: | | $1,2$ | $100$ | $100$ | $3$ | | $3,4$ | $100$ | $10^3$ | $3$ | | $5,6$ | $100$ | $10^4$ | $3$ | | $7,8$ | $500$ | $10^4$ | $3$ | | $9,10$ | $10^3$ | $10^4$ | $3$ | | $11,12$ | $10^4$ | $10^5$ | $3$ | | $13\sim 16$ | $10^5$ | $10^6$ | $0$ | | $17\sim 21$ | $10^5$ | $10^6$ | $3$ | | $22,23$ | $10^5$ | $10^9$ | $100$ | | $24,25$ | $10^6$ | $10^9$ | $100$ | 保证测试点 $13\sim 16$ 的 $x_i$ 为随机构造。 测试点 $24,25$ 的时间限制为 $3\text s$ ，其他测试点的时间限制均为 $2\text s$。 对于 $100\%$ 的数据，满足 $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$。 **注意：数轴上同一个位置上可能会多次增添标记。** **已自动开启 $\text{O2}$ 优化，保证时空限制均为 $\text{std}$ 在开启 $\text{O2}$ 优化后的两倍以上。**