В вагоне поезда есть $$$n$$$ мест, на каждом месте сидит ровно один человек. Места пронумерованы слева направо от $$$1$$$ до $$$n$$$. Поездка долгая, поэтому каждый человек в какой-то момент поездки проголодается и захочет заварить лапшу быстрого приготовления кипятком. Человек на месте $$$i$$$ ($$$1 \leq i \leq n$$$) захочет выйти за кипятком ровно на $$$t_i$$$-й минуте.

Бак с кипятком находится левее $$$1$$$-го места за дверью. Люди, выходящие за кипятком, могут образовывать очередь у бака в порядке выхода, так как баком может одновременно пользоваться не более одного человека. Каждый человек пользуется баком ровно $$$p$$$ минут. Можно считать, что люди выходят к баку или возвращаются на своё место после получения кипятка мгновенно.

Люди не любят просто так стоять в очереди. Поэтому, как только человек на месте с номером $$$i$$$ захочет сходить за кипятком, он сначала посмотрит на все места с номерами от $$$1$$$ до $$$i - 1$$$. Если хотя бы одно из этих мест пустое, он предполагает что все эти люди стоят в очереди, а значит выходить за кипятком пока нецелесообразно. Тем не менее, он выйдет за кипятком в ближайший удобный момент, как только все места с номерами меньше $$$i$$$ будут снова заняты. Люди не видят самого бака и очереди возле него за дверью, поэтому смотрят только на места в вагоне.

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

Задача состоит в том, чтобы для каждого человека определить, на какой минуте он получит кипяток для своей лапши.