На палубе пираты
На палубе пираты
В древние века землю населяли две команды пиратов: Буканеры и Бербэри. Число пиратов в командах не было фиксированным, иногда противники нападали друг на друга и превращали пленных в членов своей команды. Однажды в пиратской земле появился волшебник, который начал совершать переход пиратов из одной команды в другую по собственному желанию. Для этого были использованы необходимые заклинания. Процесс смены команды назывался мутацией.
Всего имеется n пиратов, каждый из которых имеет уникальный идентификационный номер id от 0 до n - 1. Великий маг может видоизменять набор пиратов с последовательными идентификационными номерами на другой.
Пусть на земле имеются 100 пиратов, и все они являются Бербэри пиратами. Маг совершает заклинание, которое изменяет пиратов с id от 10 до 33 на Буканеров. Теперь во всей земле имеются 24 Буканеров и 76 Бербэри пиратов.
Волшебник начал слишком быстро выполнять заклинания. Однажды Богу не понравилось это. Бог был милостив к Буканерам и спросил волшебника "Скажи мне, сколько пиратов с индексами от 2 до 30 являются Буканерами?". Теперь маг был озадачен, поскольку он был эффективен только в заклинаниях, но не в подсчете :-).
Будучи достаточно умным, маг захватил умного человека из планеты Земля. К сожалению, это были Вы! Теперь Вы должны ответить на вопросы Богов.
Входные данные
Первая строка содержит количество тестов t. Структура каждого теста следующая:
Первая часть входных данных описывает пиратскую землю. Она содержит до n (1 ≤ n ≤ 1024000) пиратов. Каждый пират принадлежит или команде Буканеров или Бербэри. Буканеры пираты обозначаются '1' (ОДИН), а Бербэри пираты обозначаются '0' (НОЛЬ). Вам следует построить строку пиратов из входных данных. Каждый тест начинается числом m (m ≤ 100), за которым следует m пар строк. В каждой паре строк (будем называть ее набором), первая содержит целое число t (t ≤ 200), а вторая - непустую строку пиратов (состоящую из 0 и 1, 0 - Бербэри, 1 - Буканеры, ее длина не более 50). Совершите конкатенацию этой строки с собой t раз. Теперь сконкатенируйте результирующие m наборов строк и получите строку - описание пиратов. Финальное объединение строк описывает пиратов начиная с индекса 0 и до конца (индекс n - 1 для n-го пирата).
Следующая часть входных данных содержит вопросы. Первая строка єтой части содержит количество вопросов q. Каждая из следующих q (1 ≤ q ≤ 1000) строк содержит один вопрос. Каждый вопрос начинается одной из букв F, E, I или S, за которой следуют два целых числа - индексы a и b. Значение этих запросов следующее:
F a b означает мутировать пиратов с индексами от a до b в Буканер пиратов.
E a b означает мутировать пиратов с индексами от a до b в Бербэри пиратов.
I a b означает мутировать пиратов с индексами от a до b в инвертированных пиратов.
S a b означает "вопрос Бога", Бог задает вопрос: "Скажи мне сколько Буканеров находится среди пиратов с индексами от a до b?"
(a ≤ b, 0 ≤ a < n, 0 ≤ b < n, границы диапазона включительно)
Выходные данные
Для каждого теста вывести его номер. Для каждого вопроса Бога вывести в отдельной строке его номер, двоеточие (:), пробел и ответ на вопрос.
2 2 5 10 2 1000 5 F 0 17 I 0 5 S 1 10 E 4 9 S 2 10 3 3 1 4 0 2 0 2 I 0 2 S 0 8
Case 1: Q1: 5 Q2: 1 Case 2: Q1: 0