D. Даты событий
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

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

Входные данные

В первой строке записано целое число n (1 ≤ n ≤ 100) — количество известных событий. Далее следует n строк по два целых числа li и ri в каждой (1 ≤ li ≤ ri ≤ 107) — самая ранняя допустимая дата и самая поздняя допустимая дата i-го события.

Выходные данные

Выведите n чисел — даты, в которые произошли события. Если решений несколько, выведите любое. Гарантируется, что решение существует.

Примеры
Входные данные
3
1 2
2 3
3 4
Выходные данные
1 2 3
Входные данные
2
1 3
1 3
Выходные данные
1 2