Göyərtədə quldurlar
Qədim zamanlarda iki pirat komandası vardı: Bukanyerlər və Berberilər. Bu komandaların pirat sayı sabit deyildi, çünki bəzən rəqiblər bir-birinə hücum edərək əsirləri öz komandalarına qatırdılar. Bir gün pirat torpağında bir sehrbaz peyda oldu və piratları bir komandadan digərinə keçirməyə başladı. Bunun üçün sehrlərdən istifadə olunurdu və bu proses mutasiya adlanırdı.
Cəmi n pirat var, hər biri 0-dan n - 1-ə qədər unikal identifikasiya nömrəsi id-yə malikdir. Sehrbaz ardıcıl identifikasiya nömrələrinə malik piratların dəstini digər komandaya dəyişə bilər.
Məsələn, torpaqda 100 pirat var və hamısı Berberi piratlarıdır. Sehrbaz id-ləri 10-dan 33-ə qədər olan piratları Bukanyerlərə çevirən bir sehr edir. İndi torpaqda 24 Bukanyer və 76 Berberi pirat var.
Sehrbaz sehrləri sürətlə etməyə başladı. Bir gün Tanrı bu vəziyyətdən narazı oldu. Tanrı Bukanyerlərə mərhəmət göstərdi və sehrbazdan soruşdu: "Mənə de, 2-dən 30-a qədər olan indekslərdə neçə Bukanyer var?". Sehrbaz çaşqın idi, çünki o, yalnız sehrlərdə bacarıqlı idi, amma saymaqda yox :-).
Ağıllı sehrbaz Yer planetindən ağıllı bir insanı əsir aldı. Təəssüf ki, bu siz idiniz! İndi siz Tanrının suallarına cavab verməlisiniz.
Giriş Məlumatları
Birinci sətir testlərin sayını t ehtiva edir. Hər bir testin strukturu belədir:
Giriş məlumatlarının birinci hissəsi pirat torpağını təsvir edir. O, n (1 ≤ n ≤ 1024000) pirata qədər ehtiva edir. Hər bir pirat ya Bukanyer, ya da Berberi komandasına aiddir. Bukanyer piratları '1' (BİR), Berberi piratları isə '0' (SIFIR) ilə göstərilir. Sizə giriş məlumatlarından piratların bir sıraını qurmaq lazımdır. Hər bir test m (m ≤ 100) sayı ilə başlayır, ardınca m cüt sətir gəlir. Hər bir cüt sətirdə (onu dəst adlandıraq), birinci sətir tam ədəd t (t ≤ 200), ikinci isə boş olmayan pirat sətiridir (Berberi üçün 0, Bukanyer üçün 1, uzunluğu 50-dən çox deyil). Bu sətiri özünə t dəfə birləşdirin. İndi nəticədə alınan m dəst sətirlərini birləşdirin və piratların təsvirini əldə edin. Yekun birləşmiş sətir piratları 0 indeksindən başlayaraq sonuna qədər (sonuncu pirat üçün n - 1 indeksi) təsvir edir.
Giriş məlumatlarının növbəti hissəsi sualları ehtiva edir. Bu hissənin birinci sətiri sualların sayını q ehtiva edir. Növbəti q (1 ≤ q ≤ 1000) sətirin hər biri bir sual ehtiva edir. Hər bir sual F, E, I və ya S hərflərindən biri ilə başlayır, ardınca iki tam ədəd - indekslər a və b gəlir. Bu sorğuların mənası belədir:
F a b indeksləri a-dan b-ə qədər olan piratları Bukanyer piratlarına mutasiya etmək deməkdir.
E a b indeksləri a-dan b-ə qədər olan piratları Berberi piratlarına mutasiya etmək deməkdir.
I a b indeksləri a-dan b-ə qədər olan piratları tərs piratlara mutasiya etmək deməkdir.
S a b "Tanrının sualı" deməkdir, Tanrı soruşur: "Mənə de, a-dan b-ə qədər olan indekslərdə neçə Bukanyer var?"
(a ≤ b, 0 ≤ a < n, 0 ≤ b < n, diapazonun sərhədləri daxil olmaqla)
Çıxış Məlumatları
Hər bir test üçün onun nömrəsini çıxarın. Tanrının hər bir sualı üçün ayrıca sətirdə onun nömrəsini, iki nöqtə (:), boşluq və suala cavabı çıxarın.