Divar
Djan-Ji eyni ölçüdə kərpiclərdən divar tikir. Divar, soldan sağa doğru 0-dan n - 1-ə qədər nömrələnmiş n sütundan ibarətdir. Hər bir sütunun hündürlüyü, içindəki kərpiclərin sayını göstərir. Sütunların hündürlükləri fərqli ola bilər.
Djan-Ji divarı belə tikir: Əvvəlcə heç bir sütunda kərpic yoxdur. Sonra Djan-Ji k əməliyyatı yerinə yetirir, bunlar kərpiclərin əlavə edilməsi və ya çıxarılması əməliyyatları ola bilər. Tikinti, bütün k əməliyyatları tamamlandıqda bitmiş sayılır. Hər bir əməliyyatdan əvvəl Djan-Ji ardıcıl sütunlardan ibarət bir interval və h hündürlüyünü seçir. Daha sonra aşağıdakı əməliyyatlardan birini həyata keçirir:
Əlavə əməliyyatı: Djan-Ji seçilmiş intervaldakı sütunlara, hündürlüyü h-dən az olan sütunlara kərpiclər əlavə edir ki, onların hündürlüyü h-ə bərabər olsun. Hündürlüyü h-dən az olmayan sütunlara toxunmur;
Çıxarma əməliyyatı: Djan-Ji seçilmiş intervaldakı sütunlardan, hündürlüyü h-dən çox olan sütunlardan kərpicləri çıxarır ki, onların hündürlüyü h-ə bərabər olsun. Hündürlüyü h-dən çox olmayan sütunlara toxunmur.
Divarın son formasını müəyyənləşdirmək tələb olunur.
Nümunə
Tutaq ki, 10 sütun və divarın dəyişdirilməsi üzrə 6 əməliyyat var. Sorğularda sərhədlər daxil edilir. Hər bir əməliyyatın yerinə yetirilməsindən sonra divarın vəziyyəti aşağıda göstərilmişdir.
Əvvəlcə bütün sütunların hündürlüyü sıfıra bərabər olduğundan, 0 mərhələsindən sonra 1-dən 8-ə qədər olan hər bir sütun 4 kərpicdən ibarət olacaq. 0 və 9 sütunları boş qalır.
1 mərhələsində 4-dən 8-ə qədər olan sütunlardan kərpiclər çıxarılır ki, hər biri 1 kərpicdən ibarət olsun, 9 sütunu boş qalır. 0-dan 3-ə qədər olan sütunlar sorğunun xaricindədir, buna görə də toxunulmaz qalır.
2 mərhələsində 3-dən 6-ya qədər olan sütunlarda dəyişikliklər baş vermir, çünki onlar 5 kərpicdən çox deyil.
3 əməliyyatından sonra 0, 4 və 5 sütunlarındakı kərpiclərin sayı 3-ə qədər artır.
4 əməliyyatından sonra 2 sütununda 5 kərpic var.
5 əməliyyatı 6 və 7 sütunlarındakı bütün kərpicləri çıxarır.
Giriş məlumatları
Birinci sətir iki tam ədəd n və k (1 ≤ n ≤ 2 * 10^6, 1 ≤ k ≤ 5 *10^5) ehtiva edir. n - divardakı sütunların sayı, k - əməliyyatların sayı. Növbəti k sətirdən hər biri formatdadır: op[i], left[i], right[i], height[i] (0 ≤ i ≤ k − 1). op[i] - i əməliyyatının növü: əlavə üçün 1, çıxarma üçün 2. i-ci əməliyyatda iştirak edən sütunların indeksləri left[i]-dən right[i]-ə qədər dəyişir (həm left[i], həm də right[i] daxil olmaqla). Məlumdur ki, left[i] ≤ right[i]. height[i] - i-ci əməliyyatın hündürlük parametri.
Çıxış məlumatları
n ədəd çıxarın, hər biri bir sətirdə. i-ci sətirdə i sütunundakı nəticə kərpiclərin sayını çıxarın (0 ≤ i ≤ n − 1).