Очередь

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

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

Билеты на фильм продаются в павильоне, в котором одновременно могут находиться не более $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}$.

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

Очередь

문제

입력

출력