Недавно студенты из города С. поехали на сборы в город П. Всего на сборы отправилось n студентов.
Вечером в поезде возникла очередь за чаем. Студент с номером i приходит в очередь к чайнику в начале секунды li. Студенты приходят в очередь в порядке увеличения их номеров (то есть если два студента придут в очередь в одно и то же время, первым будет тот, у кого меньше номер). Если очередь пуста — он за одну секунду наливает себе чай и уходит. Иначе же он ждёт, пока все студенты перед ним нальют себе чай и уйдут. Если в начале секунды ri i-й студент до сих пор не может налить себе чай (кто-то до сих пор перед ним в очереди), он просто уходит из очереди.
Помогите определить для каждого студента, в какой момент времени он нальёт себе чай, или же определите, что он не дождётся этого момента и покинет очередь.
Выходные данные
Для каждого набора выведите n чисел. i-е число — момент времени, в который студент i нальёт себе чай, или же 0, если студент не сможет этого сделать.
Примечание
Пример содержит 2 набора:
- В 1-ю секунду студенты 1 и 2 встают в очередь, и студент 1 наливает себе чай. Студент 2 наливает себе чай во 2-ю секунду.
- В 1-ю секунду студенты 1 и 2 встают в очередь, студент 1 наливает себе чай, и студент 2 уходит без чая. Во 2-ю секунду приходит студент 3 и наливает себе чай.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
2
1 3
1 4
3
1 5
1 1
2 3
|
1 2
1 0 2
|