After studying the characteristics of the SARS-CoV-233 virus, S-planet began to deal with people infected by it.

The SHO (S-planet Health Organization) designated the pneumonia caused by the SARS-CoV-233 virus as COVID-12243.

During this period on S-planet, numerous technological and health conferences needed to be held. Conferences on S-planet are conducted in a hierarchical manner:

First, the United Nations of S-planet proposes several issues and methods at a conference, then the presidents of each country convey these ideas to their respective provinces, and so on, down to each individual, before being summarized back up.

However, during the sessions of the National People's Congress at various levels in country $\Theta$, due to insufficient medical standards in some rural areas, some villagers have unknowingly contracted COVID-12243, yet the test reagents cannot detect it.

Little $\omega$, as the president of country $\Theta$, feels this is a very serious matter. Therefore, she will personally visit the entire route, bringing advanced reagents, and quarantine these COVID-12243 patients.

Formally, the administrative divisions of S-planet are divided into $n$ levels (equivalent to Country - Province - City - County/District - Township, etc., in China), referred to from smallest to largest as level $1$ administrative units, level $2$ administrative units, ..., level $n$ administrative units (country $\Theta$).

Now, we examine a specific route (i.e., a certain township $\to \cdots \to$ country $\Theta$), where each level of administrative unit has $k$ representatives. We denote the $j$-th representative of the $i$-th level as $(i, j)$.

It is known that representatives of adjacent levels have opportunities to meet, while representatives of non-adjacent levels (even at the same level) do not have opportunities to meet.

(ps: Representatives at the same level have special measures in place during meetings, so they will not transmit the virus even if they meet.)

For representatives of adjacent levels, little $\omega$ has already investigated: for $\forall 1 \leq i \leq n - 1, 1 \leq u, v \leq k$, whether $(i, u)$ and $(i + 1, v)$ have an opportunity to meet.

Now, several National People's Congresses need to be held in country $\Theta$. The requirements for each meeting are as follows:

First, the level $l$ administrative unit holds a meeting, then the level $l$ representatives and level $l + 1$ representatives meet in sequence, then the level $l + 1$ administrative unit begins its meeting, then they meet with the level $l + 2$ representatives in sequence, ..., until the level $r$ meeting is finished. Finally, the level $r$ representatives must report the information to little $\omega$.

Specifically, we are given two sets $P_l$ and $P_r$, indicating that in the level $l$ administrative unit, only the people in set $P_l$ participate in the entire meeting, and in the level $r$ administrative unit, only the people in set $P_r$ participate. For $\forall l < i < r$, all representatives of the $i$-th level administrative unit must participate.

However, it is known that the representatives of level $l$ have the potential to carry COVID-12243, while others do not. When two people meet, the virus spreads from the lower-level representative to the upper-level representative. This results in a certain probability that little $\omega$ will be infected with SARS-CoV-233.

Therefore, she will choose to quarantine a number of all representatives, especially some super-spreaders. Quarantined people cannot meet with anyone and can only pass information through special means.

However, the cost of quarantining a person is high, so little $\omega$ hopes to quarantine as few people as possible to ensure she will not be infected (even if the meeting cannot be successfully held).

Moreover, for various reasons, whether different people have the opportunity to meet changes constantly, but it is always maintained that only representatives of adjacent levels have the opportunity to meet.

Note: In two different meetings, the condition that "the representatives of level $l$ have the potential to carry COVID-12243" is independent and does not affect each other.

Input

The first line contains three positive integers $n, k, q$, representing the number of administrative levels, the number of representatives at each level, and the number of events.

The next $k(n - 1)$ lines are divided into $n - 1$ segments, each containing $k$ lines.

For the $i$-th ($1 \leq i \leq n - 1$) segment, the $u$-th ($1 \leq u \leq k$) line contains a $\texttt 0/\texttt 1$ string of length $k$, where the $v$-th ($1 \leq v \leq k$) character being $\texttt 1$ means $(i, u)$ and $(i + 1, v)$ have an opportunity to meet, otherwise they do not.

The next $q$ lines each describe an event in the following format:

1. T i u v indicates that the meeting opportunity between $(i, u)$ and $(i + 1, v)$ changes; if they could not meet before, they can now, and if they could meet before, they now cannot.
2. M l r P_l P_r indicates that a National People's Congress is held for administrative levels $l \sim r$. See the problem description for the specific form of the meeting, where $P_l$ and $P_r$ are $\texttt 0/\texttt 1$ strings. The $j$-th character of $P_l$ is $1$ if and only if $(l, j)$ participates in this meeting. The same applies to $r$. You need to find the minimum number of people to quarantine.

Output

For each M event, output a single integer representing the minimum number of people to quarantine.

Examples

Input 1

2 5 13
11000
00100
00100
00100
00011
M 1 2 11111 11111
M 1 2 01110 11011
M 1 2 01010 01110
T 1 2 2
T 1 4 4
M 1 2 11111 11111
M 1 2 01110 11011
M 1 2 01010 01110
T 1 2 2
T 1 4 4
M 1 2 11111 11111
M 1 2 01110 11011
M 1 2 01010 01110

Output 1

3
0
1
5
2
2
3
0
1

Note 1

The first row of dots represents level $1$ representatives, and the second row represents level $2$ representatives. If two representatives can meet, they are connected by a line segment. The resulting graph is as follows:

For the first National People's Congress, all representatives must participate. To prevent herself from being infected, little $\omega$ needs to quarantine at least three people (quarantine is indicated by yellow circles):

For the second National People's Congress, only the following $7$ representatives need to participate. Since the meeting itself cannot be successfully held, little $\omega$ does not need to quarantine anyone:

For the third National People's Congress, only the following $5$ representatives need to participate. To prevent infection, little $\omega$ only needs to quarantine $(2, 3)$:

Then, the meeting relationship between $(1, 2)$ and $(2, 2)$ changes, and the meeting relationship between $(1, 4)$ and $(2, 4)$ changes. The new relationship graph is as follows:

For the fourth National People's Congress, all representatives must participate, requiring at least $5$ people to be quarantined:

For the fifth National People's Congress, the same $7$ people participate, but this time $2$ people need to be quarantined:

For the sixth National People's Congress, $5$ people participate, and $2$ people need to be quarantined:

Then, the meeting relationships between $(1, 2)$ and $(2, 2)$, and $(1, 4)$ and $(2, 4)$ change again, so they cannot meet, and the relationship graph returns to its original state:

Thus, the number of people to quarantine for the next $3$ meetings is the same as the first $3$ meetings: $3, 0, 1$.

Input 2

3 2 10
01
10
01
10
M 1 3 10 10
M 1 3 10 01
M 1 3 01 10
M 1 3 01 01
M 1 3 11 11
M 1 2 10 10
M 1 2 10 01
M 1 2 01 10
M 1 2 01 01
M 1 2 11 11

Output 2

1
0
0
1
2
0
1
1
0
2

Note 2

Note that all representatives at intermediate levels must participate in the meeting.

Input 3

4 4 1
1000
0000
0000
0000
0100
0000
0101
0000
0000
0000
0000
0001
M 1 4 1111 1111

Output 3

0

Note 3

Note that the virus only spreads from lower-level representatives to upper-level representatives, as shown in the figure below:

Input 4

See the provided files.

Subtasks

For all test cases, $2 \leq n \leq 8192; 1 \leq k \leq 24; 1 \leq q \leq 8192; 1 \leq i \leq n - 1; 1 \leq u, v \leq k; 1 \leq l < r \leq n$.

The data scale for specific subtasks is shown in the table below: