A-hoy, Cướp biển! (Ahoy, Pirates!)

Nguồn: UVa

Phiên bản: Phước Hưng OJ Extended

Đề bài

Một chuỗi nhị phân được tạo bằng cách lặp các mẫu. Hỗ trợ gán cả đoạn thành 1, gán thành 0, đảo bit và đếm số bit 1.

Input

Dòng đầu chứa số khối $M$. Với mỗi khối, một dòng chứa số lần lặp $T$, dòng kế chứa mẫu nhị phân $P$. Nối $P$ lặp $T$ lần cho tất cả khối để được chuỗi cuối. Sau đó là số truy vấn $Q$ và $Q$ dòng c a b.

• F: gán $[a,b]$ thành 1.
• E: gán $[a,b]$ thành 0.
• I: đảo mọi bit trong $[a,b]$.
• S: đếm số bit 1 trong $[a,b]$.

Chỉ số bắt đầu từ 0.

Output

Với mỗi truy vấn S, in trực tiếp số bit 1 trên một dòng. Phiên bản PHOJ bỏ tiền tố đánh số case/query của đề gốc.

Subtask

• 20 điểm: độ dài chuỗi sau ghép $N\le50$, $Q\le50$.
• 30 điểm: $N\le5000$, $Q\le500$.
• 50 điểm: $N\le1\,024\,000$, $M\le100$, mỗi $T\le200$, $|P|\le50$, $Q\le1000$.

Ví dụ

Input

1
1
00101
7
S 0 4
F 0 1
S 0 2
I 1 3
S 0 4
E 3 4
S 0 4

Output

2
3
3
1

Giải thích

Chuỗi đầu là 00101, có 2 bit 1. Sau F 0 1 chuỗi thành 11101, nên S 0 2 cho 3. Sau khi đảo $[1,3]$ chuỗi thành 10011, có 3 bit 1; cuối cùng xóa $[3,4]$ còn 10000, nên đáp án cuối là 1.