Ahoy, Pirates!

Source: UVa

Version: Phuoc Hung OJ Extended

Problem Statement

A binary string is built from repeated patterns. Support setting a range to 1, setting it to 0, flipping it, and counting ones.

Input

The first line contains $M$ blocks. For each block, one line gives repetition count $T$ and the next line gives a binary pattern $P$. Concatenate $P$ repeated $T$ times for all blocks. Then read $Q$ and $Q$ operations c a b.

• F: set $[a,b]$ to 1.
• E: set $[a,b]$ to 0.
• I: flip all bits in $[a,b]$.
• S: count ones in $[a,b]$.

Indices are zero-based.

Output

For each S query, print the number of ones on its own line. The PHOJ version omits the original case/query labels.

Subtasks

• 20 points: expanded length $N\le50$, $Q\le50$.
• 30 points: $N\le5000$, $Q\le500$.
• 50 points: $N\le1\,024\,000$, $M\le100$, each $T\le200$, $|P|\le50$, $Q\le1000$.

Examples

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

Explanation

The initial string 00101 has 2 ones. After F 0 1 it is 11101, so S 0 2 returns 3. Flipping $[1,3]$ gives 10011 with 3 ones; clearing $[3,4]$ leaves 10000, so the final answer is 1.