Šeštadieninė informatikos olimpiadininkų mokykla

Parašykite žurnalą, su kuriuo būtų galima atlikti tokius veiksmus:

įterpti <pozicija> <skaičius> <tipas> – įterpia <skaičius> tipo <tipas> įrašų prieš įrašą, esantį pozicijoje <pozicija>. Įrašų, kurių pozicijos nemažesnės už <pozicija>, pozicijos padidėja per <skaičius>.

pašalinti <pozicija> <skaičius> – pašalina <skaičius> įrašų, pradedant nuo įrašo pozicijoje <pozicija>. Įrašų, kurių pozicijos nemažesnės už <pozicija> + <skaičius>, pozicijos sumažėja per <skaičius>.

užklausa <pozicija1> <pozicija2> – suskaičiuoja, kiek yra skirtingų tipų įrašų pozicijose nuo <pozicija1> iki <pozicija2> imtinai.

Pradiniai duomenys

Pirmoje eilutėje yra sveikasis skaičius – operacijų kiekis. Tolesnėse eilučių yra operacijų aprašai.

Kiekvienos operacijos aprašas prasideda simboliu, nurodančiu operacijos tipą:

+ – įterpti;
- – pašalinti;
? – užklausa.

Toliau pateikiami užklausos argumentai – tipas yra mažoji lotyniškos abėcėlės raidė, o kiti argumentai – sveikieji skaičiai. Pozicijos pradedamos skaičiuoti nuo 1 ir visada pateikiamos korektiškai (visose užklausos nurodytose pozicijose visada yra įrašai; niekada neliepiama ištrinti įrašų esančių už žurnalo ribų ir t. t.). Argumentas <skaičius> įterpimo ir pašalinimo operacijose niekada neviršija .

Rezultatai

Kiekvienai užklausos operacijai išveskite eilutę su vienu sveikuoju skaičiumi – kiek yra skirtingų tipų įrašų tarp <pozicija1> ir <pozicija2> imtinai.

Pavyzdžiai

8
+ 1 4 w
+ 3 3 o
? 2 3
- 2 2
? 2 3
+ 2 2 t
? 1 6
- 1 6

2
1
3