Laiko ribojimas: 3s

Atminties ribojimas: 64MB

Duomenų failas: egiptas.in

Rezultatų failas: egiptas.out

Jei norite pateikti savo sprendimą - prisijunkite.

Egiptas

Jaunasis Egipto faraonas nusprendė įsiamžinti save pasistatydamas daug piramidžių. Tam jis susirado didžiulę dykumą, kurios ilgis yra 1000000 ir pradėjo savo tarnams įsakinėti sakydamas p\\c\\w (p - fiksuotas simbolis, 1\\leqc\\leq1000000, 1\\leqw\\leq1000000, w - nelyginis skaičiu). Gavus tokį įsakymą, tarnai pastato dykumoje, ties poziciją c piramidę, kurios plotis yra w. Pavyzdžiui gavus įsakymą p\\2\\3, tarnai pastato piramidę (čia X žymi piramidės bloką):

....
.X..
XXX.

Antrą kartą gavus tokį pat įsakymą, tarnai pastato naują piramidę ant senosios:

.X..
.X..
XXX.
XXX.

Karts nuo karto faraonui atsiranda klausimas kiek blokų buvo panauda statant piramides. Šį klausimą jis taip pat užduoda savo tarnams - n\\i\\j, taip prašydamas suskaičiuoti kiek blokų buvo panaudota intervale [i;j].

Pradiniai duomenys

Pirmojoje pradinių duomenų eilutėje bus pateiktas skaičius 1\\leqN\\leq2000000, nurodantis užklausų kiekį. Likusiose N eilučių bus nurodytos užklausos pateiktos anksčiau aprašytu pavidalu.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
3
p 2 3
p 2 3
n 1 3
 
8

Pavyzdinės piramidės

p 2 1
...
.X.

p 3 3
.....
..X..
.XXX.

p 4 5
.......
...X...
..XXX..
.XXXXX.