题目描述

小 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)$。

【数据范围与约定】

保证测试点 $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}$ 优化后的两倍以上。