Šeštadieninė informatikos olimpiadininkų mokykla

Ir vėl teks pavargti su Linu ir jo hobiu kolekcionuoti unikalius skaičius :)

Šį kartą jis paėmė visus savo surinktus skaičius (kai kurie iš jų kartojasi) ir kaip karoliukus suvėrė ant ilgos virvutės. Akivaizdu, kad ši karoliukų grandinė nėra graži - joje yra pasikartojančių skaičių. Tačiau kai kurie šios grandinės posekiai atrodo tikrai neblogai, t.y. visada galima surasti posekį, kuris turės bent vieną unikalų skaičių (jei grandinę sudaro skaičiai , tai posekis [4:5] yra gražus, kadangi jame yra net du unikalūs skaičiai: ir ).

Didėjant grandinei sąlyginai mažėjo gražių posekių, tačiau Linas pastebėjo, kad jam patinka ne tik tie skaičiai, kurie unikalūs, bet ir tie, kurie kažkokiame posekyje kartojasi nelyginį kiekį kartų. Dabar jam įdomu, kiek yra gražių skaičių kažkokiame jo grandinės posekyje. Žinodamas, kad jums puikiai sekasi skaičiuoti skaičių kiekius, jis paprašė jūsų pagalbos.

Linas planuoja jums uždavinėti klausimus pavidalo , į kuriuos jums reikės atsakyti parašant kiek nelyginį kartų pasikartojančių skaičių yra posekyje prasidedančiame indeksu ir pasibaigiančiu (grandinė numeruojama nuo , yra fiksuotas simbolis). Linas taip pat gali bet kada atlikti operaciją , po kurios jo grandinės skaičius, kurio pozicija , bus pakeistas į skaičių .

Pradiniai duomenys

Pirmoje eilutėje bus du skaičiai (, ). nurodo skaičių esančių grandinėje kiekį, o - užklausų kiekį.

Antrojoje eilutėje bus pateikti vienu tarpu atskirti skaičiai (). Šie skaičiai sudarys Lino grandinę.

Likusiose eilutėse bus pateiktos Lino užklausos, kurių kiekviena bus arba () arba () pavidalo.

Rezultatai

Į kiekvieną tipo užklausą reiks atsakyti nurodant gražių skaičių kiekį nurodytam intervale (atlikus prieš šią užklausą buvusias tipo užklausas).

Pavyzdžiai

5 5
1 2 2 3 4
S 1 2
Q 1 3
Q 3 5
S 5 2
Q 1 5

1
3
1