Ad günü#3205

Ad günü

4 saniyə

122,174 meqabayt

Çətin

Stan ad günü üçün Stewiedən sehrli bir massiv hədiyyə alıb. Bu massiv iki əməliyyatı yerinə yetirə bilir: istənilən elementi dəyişmək və aşağıdakı tipli sorğunu cavablandırmaq: "aralıqda $a$ -dan $b$ -yə qədər neçə müxtəlif ədəd var?"

Stan bu hədiyyədən olduqca təsirlənib, amma eyni zamanda şübhələnir, çünki Stewienin zarafatları ilə məşhurdur. İlk baxışda hər şey qaydasında görünürdü: Stan bir neçə sadə əməliyyat edəndə massiv bütün cavabları düzgün qaytardı.

Sehrli massivi tam yoxlamaq və şübhələri aradan qaldırmaq üçün Stan sənin köməyinə müraciət edir: o, ardıcıl bir neçə əməliyyat yerinə yetirəcək, sən isə düzgün cavabları tapmalısan ki, Stan əmin ola bilsin, həqiqətən sehrli massivdir.

Giriş

Birinci sətirdə iki tam ədəd $n$ və $m$ ( $1 \leq n, m \leq 50000$ 1 \leq n, m \leq 50000) verilir. İkinci sətirdə massivə ilkin yazılmış $n$ ədəd göstərilmişdir. Növbəti $m$ sətirdə əməliyyatlar təsvir olunur:

Dəyişmə əməliyyatı: $c x z$ , burada $x$ ( $0 \leq x < n$ 0 \leq x < n) massivdə dəyişdiriləcək indeksdir, $z$ isə yeni dəyərdir.
Sorğu əməliyyatı: $q x y$ , burada $x, y$ ( $0 \leq x \leq y < n$ 0 \leq x \leq y < n) — aralıq sərhədləri olub, bu aralıqda neçə müxtəlif ədəd olduğunu tapmalısan.

Bütün massiv elementləri $1 0^{9}$ 10^9-u aşmayan qeyri-mənfi tam ədədlərdir.

Çıxış

" $q x y$ " şəklində olan hər bir sorğu üçün, Stanın sehrli massivi ilə hesablanmış cavabı ayrıca sətirdə çap et.

Nümunələr

Nümunə 1

Loading

1 \leq n, m \leq 50000

0 \leq x < n

0 \leq x \leq y < n

1 0^{9}