Ticarət#7482
Алматы-Тараз marşrutu boyunca yaşayış məntəqəsi yerləşir, -dən -ə qədər nömrələnmişdir. Qış gəldikdə naməlum tacir bir kənddən toxunma papaqları gətirib və bu yaşayış məntəqələrində satmağa başlayıb.
Tacirlər iki prinsipə əməl edirlər:
Onlar bir yerdə bir gündən çox satmırlar.
Hər gün papaq qiymətini artırırlar.
Daha dəqiq olaraq, hər bir -ci tacir:
Ticarətə l_i məntəqəsində x_i start qiyməti ilə başlayır.
Hər gün qonşu yaşayış məntəqsinə keçirlər: əvvəlki gün məntəqəsində ticarət etdilərsə, bu gün j + 1 məntəqəsində satırlar.
Hər gün qiyməti artırırlar: əgər dünən qiymət idisə, bu gün x + 1 olur.
Ticarəti r_i məntəqəsində bitirirlər (bu zaman r_i-də yenə də satırlar).
Hər bir yaşayış məntəqəsi üçün bütün ticarət tarixində bir papağın maksimal qiymətini müəyyənləşdirin.
Birinci sətirdə iki tam ədəd n~(1 \le n \le 3 \cdot 10^5) və m~(1 \le m \le 3 \cdot 10^5) — yaşayış məntəqələrinin sayı və tacirlərin sayı verilib.
Daha sonra sətir gəlir, hər biri l_i, r_i~(1 \le l_i \le r_i \le n) və x_i~(1 \le x_i \le 10^9) — -ci tacirin başlanğıc və son yaşayış məntəqələrini, həmçinin start papaq qiymətini bildirir.
tam ədəd çıxarın, burada -ci ədəd -ci yaşayış məntəqəsi üçün bütün ticarət tarixində bir papağın maksimal qiymətini bildirir. Əgər hansısa məntəqədə ticarət aparılmayıbsa, çıxarın.
Nümunə 1
Nümunə 2