На уроке истории учитель попросил Васю назвать даты, когда произошли n известных событий. Он не помнит точные даты, но для каждого события он помнит отрезок дней [li, ri] (включительно), в которые оно могло произойти. Однако еще Вася помнит, что в один день могло произойти только одно событие. Помогите ему выбрать такие n дат известных событий, чтобы оба условия выполнялись. Гарантируется, что решение существует.
Выходные данные
Выведите n чисел — даты, в которые произошли события. Если решений несколько, выведите любое. Гарантируется, что решение существует.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 2
2 3
3 4
|
1 2 3
|
|
2
|
2
1 3
1 3
|
1 2
|