Göyərtədə quldurlar#752

Göyərtədə quldurlar

1 saniyə

122,174 meqabayt

Çox asan

Quldurlar dövründə Quldurlar torpağı iki komandaya bölünmüşdü: Bukanyerlər və Barbar quldurları. Hər komandadakı quldurların sayı dəyişirdi, çünki bəzən rəqiblər hücum edib ələ keçirdikləri quldurları öz komandalarına qatırdılar. Bir gün sehrbaz peyda oldu və sehr vasitəsilə quldurların komandalarını dəyişməyə başladı. Bu prosesə mutasiya deyilirdi.

Burada $n$ quldur var, hər birinin $0$ -dan $n - 1$ n-1-ə qədər olan yeganə identifikasiya nömrəsi $i d$ var. Böyük sehrbaz ardıcıl $i d$ -lərə malik quldurların bir qrupunu digər komandaya mutasiya edə bilərdi.

Məsələn, əgər Quldurlar torpağında $100$ quldur olsa və onların hamısı Barbar quldurlarından ibarət olsa, sehrbaz bir sehr oxuyub $i d$ -si $10$ -dan $33$ -ə qədər olan quldurları Bukanyerə çevirə bilərdi. Beləliklə, nəticədə $24$ Bukanyer və $76$ Barbar qulduru olardı.

Sehrbaz sehrləri çox tez oxuyurdu. Bir gün Tanrı bu dəyişikliklərdən bezdi. Tanrı Bukanyerlərə rəğbət göstərərək soruşdu: "Bax gör, $2$ -ci indeksdən $30$ -cu indeksə qədər neçə Bukanyer var?" Sehrbaz çaşıb qaldı, çünki o, sehrə usta olsa da, saymaqda bir o qədər bacarıqlı deyildi :-).

Ona görə də sehrbaz Yer planetindən ağıllı bir insanı tutdu — bu adam da sənsən! İndi Tanrının suallarına cavab verməlisən.

Giriş

İlk sətirdə testlərin sayı $t$ verilir.

Hər bir test üçün aşağıdakı kimi məlumat verilir:

Girişin ilk hissəsi Quldurlar torpağını təsvir edir. Burada quldurların sayı $n$ -ə qədər ola bilər ( $1 \leq n \leq 1024000$ 1 \leq n \leq 1024000). Hər quldur ya Bukanyer, ya da Barbar quldurları qrupuna aiddir. Bukanyer quldurları 1 (BİR), Barbar quldurları isə 0 (SIFIR) ilə göstərilir. Quldurların təsviri sətirini aşağıdakı kimi qurmalısınız:

Hər testdə əvvəlcə $m$ ədədi ( $m \leq 100$ m \leq 100) verilir; sonra isə $m$ cüt sətr gəlir. Hər cüt aşağıdakılardan ibarətdir:

Birinci sətir: tam ədəd $t$ ( $t \leq 200$ t \leq 200)
İkinci sətir: boş olmayan $P i r a t es$ Pirates sətri (yalnız '0' və '1' simvollarından ibarət, uzunluğu maksimum $50$ )

$P i r a t es$ Pirates sətrini ardıcıl olaraq $t$ dəfə təkrar edin. Bunu bütün $m$ cüt üçün tətbiq edin, sonra alınan sətrləri ardıcıl birləşdirin və nəticədə quldur təsviri alınır. Son sətir indeksləri $0$ -dan $n - 1$ n-1-ə qədər olan quldurları təsvir edir.

Sonra isə sorğular gəlir. Bu hissənin ilk sətrində sorğuların sayı $q$ verilir.

Sonrakı $q$ ( $1 \leq q \leq 1000$ 1 \leq q \leq 1000) sətrdə hər biri bir sorğunu təsvir edir. Hər bir sorğunun formatı aşağıdakı kimidir:

F a b: $a$ -dan $b$ -yə (hər ikisi daxil olmaqla) qədər olan quldurları Bukanyerə çevir.
E a b: $a$ -dan $b$ -yə (hər ikisi daxil olmaqla) qədər olan quldurları Barbar qulduruna çevir.
I a b: $a$ -dan $b$ -yə (hər ikisi daxil olmaqla) qədər olan quldurların vəziyyətini dəyiş (0->1, 1->0).
S a b: Tanrının sualı: " $a$ -dan $b$ -yə (hər ikisi daxil olmaqla) qədər neçə Bukanyer var?"

Burada $a \leq b$ a \leq b, $0 \leq a < n$ 0 \leq a < n, $0 \leq b < n$ 0 \leq b < n.

Çıxış

Hər test üçün əvvəlcə test nömrəsini çap et. Sonra isə hər Tanrı sorğusu üçün sorğunun nömrəsini, iki nöqtə (:), bir boşluq və cavabı çap et.

Nümunələr

Nümunə 1