На палубі пірати
У давнину на землі жили дві команди піратів: Буканери та Бербері. Кількість піратів у цих командах постійно змінювалася, оскільки вони часто нападали один на одного, перетворюючи полонених на членів своєї команди. Одного разу на піратській землі з'явився чарівник, який почав переміщувати піратів з однієї команди в іншу за допомогою магічних заклинань. Цей процес називався мутацією.
На землі є 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, довжина якого не перевищує 50). Повторіть цей рядок t разів. Потім об'єднайте всі m наборів рядків, щоб отримати рядок, що описує піратів. Фінальне об'єднання рядків описує піратів з індексами від 0 до n - 1.
Наступна частина вхідних даних містить питання. Перша строка цієї частини містить кількість питань 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, межі діапазону включно)
Вихідні дані
Для кожного тесту виведіть його номер. Для кожного питання Бога виведіть в окремому рядку його номер, двокрапку (:), пробіл і відповідь на питання.