Śnieżyca

Limit pamięci: 128 MB

Jak zwykle zima zaskoczyła drogowców. W Bajtogrodzie szaleje śnieżyca i główna droga Bajtogrodu pilnie wymaga odśnieżenia.

Za porządek odpowiedzialny jest sztab antykryzysowy, mający do dyspozycji pługów, ponumerowanych liczbami od 1 do . Każdy pług ma przydzielony pewien spójny fragment drogi do odśnieżenia. Dwa fragmenty mogą na siebie nachodzić, ale żaden fragment nie zawiera się w całości w innym. Fragmenty nie muszą pokrywać całej długości drogi (niektóre części drogi mogą biec tunelami i nie wymagają odśnieżenia).

Niestety właśnie rozpoczął się strajk drogowców. Kierownictwu sztabu antykryzysowego udało się przekonać do pracy tylko jednego operatora pługu, któremu powierzono obsługę wszystkich maszyn. Teraz trzeba ustalić kolejność wyjazdu pługów. Zarządzono, że za każdym razem pracownik będzie wybierał pług, któremu pozostało najmniej do odśnieżenia z przydzielonego fragmentu drogi (wystarczy, że każdy kawałek drogi zostanie odśnieżony raz, zatem pług nie musi odśnieżać tych kawałków, które zostały wcześniej odśnieżone przez inne pługi). W przypadku remisu pracownik wybierze pług o mniejszym numerze.

Wejście

Pierwszy wiersz wejścia zawiera dwie liczby całkowite oraz (, ), oznaczające długość drogi oraz liczbę pługów. Następne wierszy opisuje kolejne pługi, o coraz większych numerach. Opis -tego pługu składa się z dwóch liczb całkowitych , (), oznaczających początek i koniec fragmentu drogi przydzielonego -temu pługowi. Możesz założyć, że , tzn. pługi są posortowane względem początku obsługiwanego fragmentu drogi. Ponadto, żaden fragment nie zawiera się w całości w innym.

Wyjście

Twój program powinien wypisać na wyjście numery pługów w kolejności odśnieżania drogi. Wyjście powinno składać się z wierszy, z których każdy powinien zawierać jedną liczbę całkowitą.

Przykład

Dla danych wejściowych:

15 4
1 6
3 7
6 11
10 14

poprawną odpowiedzią jest:

2
1
3
4