Qar fırtınası
Qış, hər zamankı kimi, Baytburq şəhərinin briqada işçilərini hazırlıqsız yaxaladı. Güclü qar fırtınası baş verdi və əsas yolun təcili olaraq qardan təmizlənməsi lazım idi.
Bu vəzifə, 1-dən m-ə qədər nömrələnmiş m qar təmizləyici maşına malik olan Təbii Fəlakətlərlə Mübarizə Departamentinə həvalə edildi. Hər bir maşın yolun ardıcıl bir hissəsini təmizləmək üçün təyin olunub. Bu hissələr bir-birini kəsə bilər, lakin heç biri digərinin içində ola bilməz. Hissələr mütləq bütün yolu əhatə etməyə bilər (yolun təmizlənməsinə ehtiyac olmayan tunellər də ola bilər).
Təəssüf ki, bütün qar təmizləyiciləri tətilə çıxmaq üzrədir. Departamentin rəhbəri yalnız bir qar təmizləyicisini tətilə qoşulmamağa razı sala bildi. Buna görə də, işləyən yeganə qar təmizləyicisinə qalanlarını idarə etmək tapşırıldı. İndi onların hansı ardıcıllıqla istifadə olunacağını müəyyən etmək vaxtıdır. Departament qar təmizləyicisinə həmişə onunla əlaqəli hissənin hələ təmizlənməmiş hissələrinin ən kiçik ümumi uzunluğuna malik olan təmizləyicini seçməyi əmr etdi (yolun bir hissəsi təmizləndikdən sonra təmizləmə prosesi bitənə qədər təmizlənmiş hesab olunur). Əgər bir neçə belə qar təmizləyici varsa, onda daha kiçik nömrəyə malik olanı seçmək lazımdır.
Giriş Məlumatları
Birinci sətir n və m (1 ≤ n ≤ 10^9, 1 ≤ m ≤ 300 000) - yolun uzunluğunu və qar təmizləyicilərinin sayını ifadə edən iki tam ədədi ehtiva edir. Növbəti m sətir artan nömrələr sırasına görə ardıcıl təmizləyiciləri təsvir edir. i-ci sətir a[i], b[i] (1 ≤ a[i] < b[i] ≤ n) iki tam ədədi ehtiva edir, bu da i-ci qar təmizləyici maşına aid yolun hissəsinin a[i]-də başladığını və b[i]-də bitdiyini göstərir. a[i] < a[i+1] olduğunu qəbul edin, yəni qar təmizləyicilər əlaqəli yol hissəsinin sol nöqtəsinə görə sıralanıb. Bundan əlavə, heç bir hissə digər qar təmizləyici ilə əlaqəli hissənin içində deyil.
Çıxış Məlumatları
Qar təmizləyicilərin istifadə ardıcıllığına görə nömrələrini çıxarın. Çıxış m sətirdən ibarət olmalıdır, hər biri bir tam ədəd ehtiva edir.