Ahoy, Pirates!#752

Ahoy, Pirates!

1 second

122.174 megabytes

Very easy

In the age of pirates, Pirate Land was divided into two teams: the Buccaneers and the Barbary pirates. The number of pirates on each team varied, as sometimes opponents would attack and turn captured pirates into members of their own team. One day, a magician appeared and started transferring pirates between teams using magic spells. This process was known as mutation.

There are $n$ pirates, each with a unique identification number $i d$ from $0$ to $n - 1$ n - 1. The great magician could mutate a group of pirates with consecutive $i d$ s into the other team.

For example, if Pirate Land has $100$ pirates and they are all Barbary pirates, the magician could cast a spell to turn pirates with $i d$ from $10$ to $33$ into Buccaneers. There would then be $24$ Buccaneers and $76$ Barbary pirates in total.

The magician was fast at casting spells. One day, God grew weary of these changes. God, having favor for the Buccaneers, asked: "Tell me, how many of the pirates from index $2$ to $30$ are Buccaneers?" The magician was puzzled, as he was skilled with spells but not with counting :-).

So the magician captured a clever human from Earth — and that person is you! Now, you must answer God's questions.

Input

The first line contains the number of test cases $t$ .

Each test case has the following structure:

The first part of the input describes Pirate Land. There may be up to $n$ ( $1 \leq n \leq 1024000$ 1 \leq n \leq 1024000) pirates. Each pirate belongs either to the Buccaneers or the Barbary pirates. Buccaneer pirates are represented by 1 (ONE), and Barbary pirates are represented by 0 (ZERO). You have to construct the pirates' description string as follows:

Each test case starts with a number $m$ ( $m \leq 100$ m \leq 100); then $m$ pairs of lines follow. Each pair consists of:

The first line: an integer $t$ ( $t \leq 200$ t \leq 200)
The second line: a nonempty string $P i r a t es$ Pirates (composed of 0 for Barbary, 1 for Buccaneer, of length at most $50$ )

Repeat the string $P i r a t es$ Pirates $t$ times and concatenate the results into a new string. Perform this for all $m$ pairs, then concatenate all resulting strings to obtain the pirate description. The final string describes the pirates by index from $0$ to $n - 1$ n - 1.

The next part contains the queries. The first line of this part contains the number of queries $q$ .

Each of the following $q$ ( $1 \leq q \leq 1000$ 1 \leq q \leq 1000) lines describes a query. Each query is in one of the following formats:

F a b: mutate the pirates from index $a$ to $b$ (inclusive) into Buccaneers.
E a b: mutate the pirates from index $a$ to $b$ (inclusive) into Barbary pirates.
I a b: invert the pirates from index $a$ to $b$ (inclusive).
S a b: God's query: "Tell me, how many Buccaneers are there from index $a$ to $b$ (inclusive)?"

Where $a \leq b$ a \leq b, $0 \leq a < n$ 0 \leq a < n, $0 \leq b < n$ 0 \leq b < n.

Output

For each test case, output its number. For each of God's queries, output its number, a colon (:), a space, and the answer.

Examples

Example 1