38 tutuquşu
Hər kəs meşə sakinlərinin Udavın uzunluğunu tutuquşularla ölçdüyü hekayəni bilir. İndi də onlar yenidən bunu sınamaq istəyirlər. Bu dəfə onlar ən böyük tutuquşuları götürəcəklər ki, mümkün qədər az sayda olsun. Özləri ölçəcəklər, amma tutuquşular çoxluğundan ən böyüyünü seçmək kifayət qədər çətin bir vəzifədir, buna görə də siz onlara kömək etməlisiniz.
Sizdən tələb olunan tək şey, müəyyən bir aralıqda ən böyük tutuquşunun uzunluğunu tapmaqdır (çünki bütün tutuquşular bu maraqlı ideyada iştirak etmək istəmir), həmçinin bu cür tutuquşuların sayını (onlardan birini seçə bilmələri üçün).
Giriş verilənləri
Birinci sətirdə N (1 ≤ N ≤ 10^9) – tutuquşuların sayı verilir. Bütün tutuquşuların uzunluğu əvvəlcə on santimetrə bərabərdir. İkinci sətirdə M (1 ≤ M ≤ 10^5) – sorğuların sayı verilir. Hər bir sorğu üç ədəddən ibarətdir – x, l, r. Əgər x dəyəri birə bərabərdirsə, onda sizdən bir sətirdə iki ədəd çıxış etməyiniz tələb olunur – [l; r] aralığında tutuquşuların maksimum uzunluğu və bu aralıqda həmin uzunluğa malik tutuquşuların sayı, bu aralığın başlanğıcın alt aralığı olacağına zəmanət verilir. Əgər x dəyəri iki bərabərdirsə, onda l nömrəli tutuquşunun uzunluğu dəyişib və indi r bərabərdir. l nömrəli tutuquşunun mövcud olduğuna və r ədədinin heç vaxt 2·10^9 dəyərini aşmayacağına zəmanət verilir.
Çıxış verilənləri
Bir nömrəli hər bir sorğu üçün iki ədəd çıxış edin – sorğuya cavab.