Ad günü
Kiçik Styu doğum günü üçün dostu Stenə sehrli bir massiv hədiyyə etdi. Bu massiv iki əsas funksiyanı yerinə yetirə bilir: istənilən elementi dəyişdirmək və "a-dan b-yə qədər olan aralıqda neçə fərqli rəqəm var" sorğusuna cavab vermək.
Sten bu hədiyyədən çox təsirləndi, lakin Styu-nun bir hiylə qurub-qurmadığını düşünür, çünki o, əvvəllər tez-tez dostunu aldadırdı. İlk baxışda hər şey qaydasında görünürdü: Sten bir neçə sadə əməliyyat yerinə yetirdi və massiv tamamilə düzgün cavablar verdi.
Bütün şübhələri aradan qaldırmaq üçün Sten sizin köməyinizə müraciət edir: o, hədiyyə olunan massivi mükəmməl şəkildə sınaqdan keçirmək üçün bir sıra əməliyyatlar yerinə yetirmək istəyir. Siz düzgün cavablar hazırlamalısınız ki, Sten massivin həqiqətən sehrli olub-olmadığını dəqiq müəyyən edə bilsin.
Giriş Məlumatları
Birinci sətirdə iki tam ədəd n və m (1 ≤ n, m ≤ 50000) verilir. İkinci sətirdə massivin başlanğıc məzmununu təşkil edən n ədəd verilir. Növbəti m sətir əməliyyatların təsvirini ehtiva edir:
massivdə dəyişiklik əməliyyatı c x z şəklindədir, burada x – massivin cari dəyərinin z ədədi ilə əvəz olunmalı olduğu mövqedir (0 ≤ x < n);
sorğu əməliyyatı q x y şəklindədir, burada x, y (0 ≤ x ≤ y < n) tam ədədlərdir, müvafiq olaraq başlanğıc və son aralıqdır, burada fərqli rəqəmlərin sayını hesablamaq lazımdır.
Massivdəki bütün ədədlər 10^9-dan böyük olmayan qeyri-mənfi tam ədədlərdir.
Çıxış Məlumatları
Hər bir "q x y" sorğusu üçün Stenin sehrli massivi tərəfindən hesablanmalı olan nəticəni ayrı-ayrı sətirlərdə çıxarın.