На уроке истории учитель попросил Васю назвать даты, когда произошли 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
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач