시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB21150.000%

문제

Совсем недавно вышел новый фильм --- <<Люди на каникулах>>. По этому поводу Мэйвис решила сходить в кинотеатр.

Оказалость, что Мэйвис далеко не единственная, кто хочет посмотреть этот фильм. За билетами была огромная очередь. Мэйвис решила, что посмотрит кино в следующий раз, а пока она просто понаблюдает за очередью.

Билеты на фильм продаются в павильоне, в котором одновременно могут находиться не более $m$ монстров. Монстры внутри павильона обслуживаются в порядке очереди. То есть, если $i$-й монстр зашел в павильон раньше $j$-о, то монстр с номером $i$ купит билет раньше монстра с номером $j$. Монстры очень привередливы, поэтому на выбор билета у $i$-о монстра уходит $h_i$ минут.

Если $i$-й монстр подходит к павильону в момент времени $t_i$ и в павильоне в это время ровно $m$ монстров, то он уходит и возвращается через $k$ минут, то есть к моменту времени $t_i + k$. Иначе монстр заходит в павильон. Монстры очень упорные, поэтому каждый монстр будет возвращаться, пока не купит билет. Если несколько монстров подходят к павильону в одно и то же время, то сначала пытается зайти монстр с меньшим номером. Если $i$-й монстр в павильоне завершил покупку, и в это же время к павильону подходит $j$-й монстр, то сначала $i$-й выходит, а потом $j$-й пытается войти.

Мэйвис стало интересно, в какой момент времени каждый монстр купит билет. Помогите ей удовлетворить любопытство!

입력

В первой строке входного файла даны три целых числа $n$, $m$, $k$ ($1 \le n, m \le 10^5, 1 \le k \le 10^9$) --- количество монстров, максимальное число монстров в павильоне и время, на которое уходит не поместившийся монстр.

В следующих $n$ строках дано описание монстров.

В $i+1$-й строке даны два целых числа $t_i$, $h_i$ ($1 \le t_i, h_i \le 10^9$) --- время, в которое приходит $i$-й монстр в первый раз и время, которое он тратит на покупку билета.

Гаранитируется, что $t_i \le t_{i+1}$.

Монстры пронумерованы в порядке, в котором они идут во входных данных.

출력

Выведите $n$ строк. В $i$-й строке выведите время, в которое $i$-й монстр купит билет.

예제 입력 1

7 3 4
0 5
7 3
8 7
9 6
10 10
13 10
14 10

예제 출력 1

5
10
17
23
33
43
53

예제 입력 2

5 1 6
0 7
1 2
1 6
1 7
6 2

예제 출력 2

7
9
25
32
14

예제 입력 3

3 3 100
0 1
0 1
0 1

예제 출력 3

1
2
3