İyirminci əsr başlayır
XX əsrin başlanğıcıdır. Siyasət və beynəlxalq əlaqələrə qarışmış yeni, daha təhlükəli cinayətkarlar ortaya çıxır. Bir gün, bu cinayətkarlardan biri böyük müharibəyə səbəb ola biləcək çox vacib bir sənədi oğurlayır. Bu işə ən yaxşı detektivlər Şerlok Holms və doktor Vatson cəlb edilir.
Şerlok Holms doktor Vatsonla birlikdə cinayət yerinə gəlir. Oğurlanmış sənəd qapalı seyfdə idi, cinayətkar xüsusi bir cihaz vasitəsilə seyfi aça bilmişdi, amma tələsik cihazı orada unutmuşdu. Holms cihazı götürərək onun n sayda rəqəmlərlə doldurulacaq hüceyrələri olduğunu və iki funksiyaya malik olduğunu öyrənir:
p-ci elementi d qədər artırmaq, lakin bu əməliyyatı yerinə yetirərkən cihaz nədənsə əvvəlki vəziyyəti yadda saxlayırdı, yəni əvvəlki məlumat itirilmirdi;
[l, r] intervalında rəqəmlərin cəmini hesablamaq.
Cihaz bütün əvvəlki vəziyyətləri saxladığı üçün bu funksiyalarla cihazın istənilən vəziyyətinə müraciət etmək mümkün idi.
Cihaz çox sürətli işlədiyi üçün Holms düşündü ki, əgər alqoritmi başa düşsə, cihazı hazırlayan şəxsi müəyyən edə bilər. Sizin vəzifəniz bu alqoritmi yazmaqdan ibarətdir.
Giriş verilənləri
Birinci sətir iki ədəd n (1 ≤ n ≤ 100000) və m (1 ≤ m ≤ 100000) ehtiva edir, burada n — cihazın hüceyrələrinin sayı, m — sorğuların sayı.
Növbəti m sətirdə iki növ sorğular verilir:
1 x p d - x vəziyyətindən yeni bir vəziyyət yaratmaq, burada p-ci elementi d qədər artırmaq.
2 x l r - x vəziyyətində [l, r] intervalında cəmi hesablamaq;
Əvvəlcə cihazın bütün hüceyrələri sıfırlarla doldurulmuşdur. Bu vəziyyət 0 nömrəsinə malikdir. Cihazın hüceyrələrinin bütün mövqeləri birlə başlayır. Mövcud olmayan vəziyyətlərə sorğular olmayacaq. İkinci növ sorğunun işlənməsi zamanı yeni bir vəziyyət yaradılır və bu vəziyyət j + 1 nömrəsini alır, burada j - son əlavə edilmiş vəziyyətin nömrəsidir, əvvəlcə j = 0.
Çıxış verilənləri
Birinci növ sorğular üçün hər bir cavabı ayrıca sətirdə çıxış edin.