На палубі пірати#752

На палубі пірати

1 секунда

122,174 мегабайта

Дуже легка

У давнину Піратська земля була поділена на дві команди: Буканіри та пірати Барбарії. Кількість піратів у кожній команді змінювалась, адже супротивники іноді нападали та перетворювали захоплених піратів на членів своєї команди. Одного дня з'явився чарівник і почав переміщати піратів між командами за допомогою магічних заклинань. Цей процес називався мутацією.

Є $n$ піратів, кожен має унікальний ідентифікаційний номер $i d$ від $0$ до $n - 1$ n-1. Великий маг міг мутувати групу піратів із послідовними $i d$ у іншу команду.

Наприклад, якщо Піратська земля має $100$ піратів, і всі вони пірати Барбарії, чарівник міг накласти закляття і перетворити піратів із $i d$ від $10$ до $33$ на Буканірів. Тоді всього стало би $24$ Буканірів і $76$ піратів Барбарії.

Маг швидко накладав закляття. Одного дня Бог втомився від змін. Бог, прихильний до Буканірів, запитав: "Скажи-но, скільки з піратів від індексу $2$ до $30$ є Буканірами?" Маг розгубився, адже в закляттях він був вправний, а от з підрахунками вже ні :-).

Тоді він захопив розумну людину з планети Земля — і цією людиною є ти! Тепер тобі потрібно відповідати на Божі питання.

Вхідні дані

Перший рядок містить кількість тестів $t$ .

Кожен тест має таку структуру:

Перша частина вхідних даних описує Піратську землю. Піратів може бути до $n$ ( $1 \leq n \leq 1024000$ 1 \leq n \leq 1024000). Кожен пірат належить або до Буканірів, або до піратів Барбарії. Буканіри позначаються 1 (ОДИН), а пірати Барбарії — 0 (НУЛЬ). Необхідно побудувати рядок опису піратів так:

Кожен тест починається з числа $m$ ( $m \leq 100$ m \leq 100), далі йдуть $m$ пар рядків. Кожна пара складається з:

Перший рядок: ціле число $t$ ( $t \leq 200$ t \leq 200)
Другий рядок: непорожній рядок $P i r a t es$ Pirates (складається з 0 для піратів Барбарії, 1 для Буканірів, довжина не перевищує $50$ )

Рядок $P i r a t es$ Pirates потрібно повторити $t$ разів і об'єднати у новий рядок. Зробити це для всіх $m$ пар, потім з'єднати отримані рядки для формування фінального опису піратів. Остаточний рядок описує піратів за індексами від $0$ до $n - 1$ n-1.

Далі йдуть запити. Перший рядок цієї частини містить кількість запитів $q$ .

Далі йдуть $q$ ( $1 \leq q \leq 1000$ 1 \leq q \leq 1000) рядків. Кожен із них описує запит у такому форматі:

F a b: змінити піратів із індексів $a$ по $b$ (включно) на Буканірів.
E a b: змінити піратів із індексів $a$ по $b$ (включно) на піратів Барбарії.
I a b: інвертувати піратів із індексів $a$ по $b$ (включно).
S a b: Боже питання: "Скільки Буканірів серед піратів від $a$ до $b$ (включно)?"

Де $a \leq b$ a \leq b, $0 \leq a < n$ 0 \leq a < n, $0 \leq b < n$ 0 \leq b < n.

Вихідні дані

Для кожного тесту виводьте його номер. Для кожного Божого питання виводьте його номер, двокрапку (:), пробіл і відповідь.

Приклади

Приклад 1