Fırtına#6479
Qış, adət üzrə, Baytburq şəhər işçilərini hazırlıqsız tutdu. Fırtına başladı və əsas yolun təcili qar təmizliyinə ehtiyacı var.
Bu işə Təbii Fəlakətlərlə Mübarizə Departamenti cavabdehdir və onun ixtiyarında sayda qar təmizləmə maşını var, -dən -ə qədər nömrələniblər. Hər bir maşına əsas yolun ardıcıl bir hissəsi uyğun gəlir. Bu hissələr kəsişə bilər, lakin heç biri tamamilə başqa birinin içində mövcud deyil. Bu hissələr mütləq yolu tam əhatə etmirlər (yolun bəzi hissələri tunellərlə keçə bilər ki, onlar təmizləməyə ehtiyac yoxdur).
Təəssüf ki, bütün qar təmizləyiciləri tətil elan etməyə hazırdırlar. Departament rəhbəri onlardan yalnız birini tətilə qoşulmamağa razı saldı. İndi ona digər maşınları idarə etmək tapşırıldı. İndi onları hansı sırada istifadə edəcəklərini müəyyənləşdirmək lazımdır.
Departamentin göstərişinə uyğun olaraq, qar təmizləyici həmişə onunla bağlı olan hissənin hələ təmizlənməmiş hissələrinin ümumi uzunluğu ən kiçik olan maşını seçməlidir (yolun bir hissəsi təmizləndikdən sonra sonrakı təmizliyə qədər tam təmiz sayılır). Əgər belə maşın bir neçədirsə, nömrəsi daha kiçik olanı seçilməlidir.
Birinci sətir iki tam ədəd və m~(1 \le n \le 10^9,\ 1 \le m \le 3 \cdot 10^5) — yolun uzunluğu və qar təmizləmə maşınlarının sayını ehtiva edir.
Növbəti sətir maşınları nömrələrinin artan sırasına görə təsvir edir. -ci sətir a_i və b_i (1 \le a_i < b_i \le n) iki tam ədədini ehtiva edir — bu, -ci maşının cavabdeh olduğu yolun hissəsidir. a_i < a_{i+1} olduğunu hesab edin, yəni maşınlar müvafiq hissələrin sol sərhədinə görə sıralanmışdır. Bundan əlavə, heç bir hissə başqa birinin içində tamamilə mövcud deyil.
Qar təmizləmə maşınlarının istifadəsi sırasına görə nömrələrini çap edin. Cavab sətir ehtiva etməlidir, hər birində bir tam ədəd göstərilməlidir.
Nümunə 1