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

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

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

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

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

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

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

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

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

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

Оцінювання

• 20%, ~K,N \le 10~, тести 1-8
• 20%, ~K,N \le 1000~, тести 9-11
• 60%, без додаткових обмежень, тести 9-17

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

1 1
2 5

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

1

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

1 2
2 5
5 6

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

0 2

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

2 3
1 3
2 6
4 5

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

1
2
1