Очередь

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

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

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

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

Очередь

문제

입력

출력