В вагоне поезда есть \(n\) мест, на каждом месте сидит ровно один человек. Места пронумерованы слева направо от \(1\) до \(n\). Поездка долгая, поэтому каждый человек в какой-то момент поездки проголодается и захочет заварить лапшу быстрого приготовления кипятком. Человек на месте \(i\) (\(1 \leq i \leq n\)) захочет выйти за кипятком ровно на \(t_i\)-й минуте.
Бак с кипятком находится левее \(1\)-го места за дверью. Люди, выходящие за кипятком, могут образовывать очередь у бака в порядке выхода, так как баком может одновременно пользоваться не более одного человека. Каждый человек пользуется баком ровно \(p\) минут. Можно считать, что люди выходят к баку или возвращаются на своё место после получения кипятка мгновенно.
Люди не любят просто так стоять в очереди. Поэтому, как только человек на месте с номером \(i\) захочет сходить за кипятком, он сначала посмотрит на все места с номерами от \(1\) до \(i - 1\). Если хотя бы одно из этих мест пустое, он предполагает что все эти люди стоят в очереди, а значит выходить за кипятком пока нецелесообразно. Тем не менее, он выйдет за кипятком в ближайший удобный момент, как только все места с номерами меньше \(i\) будут снова заняты. Люди не видят самого бака и очереди возле него за дверью, поэтому смотрят только на места в вагоне.
В поезде действует негласное правило: если в какой-то момент возникает ситуация, что за кипятком одновременно могут выйти несколько человек, то выходит только самый левый из них (имеющий место с наименьшим номером), а остальные остаются дожидаться следующего подходящего момента.
Задача состоит в том, чтобы для каждого человека определить, на какой минуте он получит кипяток для своей лапши.
Выходные данные
Выведите \(n\) целых чисел, \(i\)-е из которых — время в минутах, когда человек на месте \(i\) получит кипяток.
Примечание
В примере в \(0\)-ю минуту за кипятком одновременно захотели пойти \(1\)-й и \(5\)-й человек, первый вышел сразу и на \(314\)-й минуте вернулся от бака. За это время множество желающих выйти за кипятком пополнилось \(2\)-м человеком, и следующим пошел \(2\)-й человек и т.д. \(5\)-й человек в итоге вышел последним.