Рядом с университетом находится остановка маршрутки. Пары закончились, и n студентов приходят на остановку. i-ый студент появляется на остановке в момент времени ti (все ti различны).
Будем считать, что остановка находится в точке координатной прямой x = 0, а маршрутка ходит вдоль луча Ox, то есть в сторону положительного направления координатной прямой и обратно. i-ому студенту нужно попасть в точку с координатой xi (xi > 0).
Маршрутка перемещается по следующему алгоритму. Изначально она находится в точке 0. Студенты последовательно приходят на остановку и садятся в нее. Как только в маршрутку сядет m студентов или сядет последний студент из n, она отправится в сторону положительного направления координатной прямой. Маршрутка двигается со скоростью 1 единица расстояния в 1 единицу времени, то есть за время y она проезжает расстояние y.
Каждый раз, когда маршрутка проезжает точку, в которой нужно выйти хотя бы одному студенту, она останавливается, и эти студенты выходят. На высадку студентов тратится 1 + [k / 2] единиц времени, где k — количество студентов, которые выходят в этой точке. Запись [k / 2] обозначает целую часть при делении k на 2. Как только из маршрутки выходит последний студент, она разворачивается и едет без остановок обратно в точку x = 0. Там она вновь наполняется студентами, и история повторяется.
Если студенты приходят на остановку, когда маршрутки там нет, они встают в очередь и садятся в маршрутку в том порядке, в котором они пришли. Посадка любого количества студентов и остальные действия происходит мгновенно, а других пассажиров нет.
Напишите программу, которая определит для каждого студента момент времени, когда он вышел из маршрутки. Моментом выхода студента из маршрутки считайте момент ее остановки в точке выхода студента (несмотря на то, что высадка группы студентов произойдет не мгновенно).
Выходные данные
Выведите n чисел w1, w2, ..., wn, wi — момент времени, когда i-ый студент вышел из маршрутки. Числа выводите в одну строку и разделяйте единичными пробелами.
Примечание
В первом примере маршрутка ждет первого студента 3 единицы времени и отвозит его до места назначения за 5 единиц времени. То есть студент выходит из маршрутки в момент времени 3 + 5 = 8.
Во втором примере вместимость маршрутки равна 1, поэтому сначала она повезет одного первого студента. Этот студент — такой же, как студент в первом примере, то есть маршрутка доезжает до его места назначения в момент времени 8, тратит на высадку 1 + [1 / 2] = 1 единицу времени, и возвращается назад еще за 5 единиц времени. Таким образом, маршрутка возвращается назад в момент времени 14. К этому моменту второй студент уже подошел к остановке, поэтому он садится в маршрутку, 5 единиц времени едет до места назначения, и приезжает в момент 14 + 5 = 19.
В третьем примере маршрутка ждет четвертого студента 6 единиц времени, затем едет 5 единиц времени, затем высаживает студентов за 1 + [4 / 2] = 3 единиц времени, возвращается за 5 единиц времени, везет пятого студента 1 единицу времени.