На вокзалі є \(K\) глухих кутів, куди прибувають електрички. Цей вокзал є їхньою кінцевою станцією, тому електрички, прибувши, деякий час стоять на вокзалі, а потім вирушають у новий рейс (у той бік, звідки прибули).

Дано розклад руху електричок, в якому для кожної електрички вказано час її прибуття, а також відправлення в наступний рейс. Електрички у розкладі впорядковані за часом прибуття. Оскільки вокзал — кінцева станція, то електричка може стояти на ньому досить довго, зокрема, електричка, яка прибуває раніше за іншу, вирушати назад може значно пізніше.

Тупики пронумеровані числами від 1 до \(K\). Коли електричка прибуває, її ставлять у вільний глухий кут з мінімальним номером. При цьому якщо електричка з якогось глухого кута вирушила в момент часу \(X\), то електричку, яка прибуває в момент часу \(X\), в цей глухий кут ставити не можна, а електричку, що прибуває в момент \(X+1\) - можна.

Напишіть програму, яка за даним розкладом для кожної електрички визначить номер глухого кута, куди прибуде ця електричка.

Формат вхідних даних

Спочатку вводяться число \(K\) - кількість тупиків і число \(N\) - кількість електропоїздів (\(1≤K≤100000\), \(1≤N≤100000\)).

Далі слідують \(N\) рядків, у кожному з яких записано по 2 числа: час прибуття та час відправлення електрички. Час задається натуральним числом, що не перевищує \(10^9\). Ніякі дві електрички не прибувають в один і той же час, але при цьому кілька електричок можуть вирушати в один і той же час. Також можливо, що якась електричка (або навіть кілька) вирушають у момент прибуття якоїсь іншої електрички. Час відправлення кожної електрички строго більший за час її прибуття.

Усі електрички впорядковані за часом прибуття. Вважається, що в нульовий момент часу всі тупики на вокзалі вільні.

Формат вихідних даних

Виведіть \(N\) чисел - по одному для кожної електрички: номер глухого кута, куди прибуде відповідна електричка. Якщо тупиків недостатньо для того, щоб організувати рух електричок згідно з розкладом, виведіть два числа: перше має дорівнювати 0 (нулю), а друге містити номер першої з електричок, яка не зможе прибути на вокзал.

Приклад вхідних даних

1 1
2 5

Приклад вихідних даних

1

Приклад вхідних даних

1 2
2 5
5 6

Приклад вихідних даних

0 2

Приклад вхідних даних

2 3
1 3
2 6
4 5

Приклад вихідних даних

1
2
1