29166번 - Загрузка лекций 스페셜 저지다국어

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

Внимательно все изучив, Мистер Бин понял, что всего есть $n$ лекций, которые он хочет скачать, $i$-я из этих лекций весит $a_i$ мегабайт. Скорость загрузки данных на компьютере Мистера Бина составляет $v$ мегабайт в секунду. Загружаемые данные грузятся параллельно, то есть если в данный момент времени загружается одна лекция, скорость загрузки данных будет равна $v$ мегабайт в секунду. Если же в данный момент загружаются две лекции, скорость загрузки данных будет равна $\frac{v}{2}$ для каждой из этих двух лекций. В общем случае, если в данный момент загружаются $k$ лекций, каждая лекция загружается со скоростью $\frac{v}{k}$ мегабайт в секунду.

Мистер Бин прикинул, когда ему будет удобно ставить на загрузку каждую из лекций, и теперь для каждого файла он хочет узнать, когда закончится его загрузка.

В первой строке входного файла содержатся два целых числа $n, v$ ($1 \le n \le 100\,000, 1 \le v \le 10^9$) --- количество лекций, которые собирается загрузить Мистер Бин и скорость загрузки (в мегабайтах в секунду).

В следующих $n$ строках входного файла содержится информация о лекциях и начале их загрузки: в $i+1$-й строке входного файла дано два целых числа $s_i, w_i$ ($1 \le s_i, w_i \le 10^9$) --- время в секундах, когда Мистер Бин поставит на загрузку $i$-й файл, и размер этого файла в мегабайтах.

Гарантируется, что для всех $1 \le i \le n-1$ верно, что $s_i \le s_{i+1}$.

Если в какую-то секунду одна лекция заканчивает свою загрузку и начинается загрузка другой, то сначала заканчивается загрузка первой, а потом начинается загрузкой второй лекции (все действия происходят в одну и ту же секунду).

В выходной файл выведите $n$ чисел, $i$-е из которых означает время окончания загрузки $i$-го файла в секундах. Ответ будет считаться верным, если он имеет относительную или абсолютную погрешность не более $10^{-6}$.