Problem G
Rivers 2

In Byteotia there are $n$ rivers flowing from south to north along the straight lines $x = i$ for ($i = 1, 2, \ldots , n$) and $m$ rivers flowing from west to east along the straight lines $y = j$ (for $j = 1, 2, \ldots , m$). At each intersection of rivers there is a city. In each city, the rivers run through tunnels and they do not mix with each other. In the past, each city drew water from the rivers over which it lay. Unfortunately, nowadays some rivers are polluted to the extent that they cannot be treated, so cities must supply water from other rivers. The cost of supplying water from a river to a city is equal to the distance of the city from the straight line along which the river flows.

Unfortunately, Byteotia has a limited budget and may not be able to deliver water to all cities. The situation is complicated by the fact that some rivers at some times are cleaned, and some are polluted again.

Write a program that will load the current state of the rivers and allow you to perform operations of two types: changing the state of a river and answering a query about the maximum number of cities to which water can be delivered for a given budget.

Input

The first line of the input gives three integers $n$, $m$, and $z$ ($1\leq n, m, z \leq 100\, 000$) specifying respectively: the number of rivers flowing in the north direction, the number of rivers flowing in the east direction, and the number of operations to be processed.

The second line contains a word of length $n$ made up of the characters + and - (plus and minus); the $i$-th character denotes the state of the $i$-th river flowing north: the plus sign denotes a clean river and the minus sign denotes a polluted river. The third line contains a word of length $m$ describing the initial state of the east-flowing rivers, in an analogous format.

The following $z$ lines contain descriptions of operations in one of the following formats:

• Z $c$ – a query for the maximum number of cities to which water can be delivered with a budget of $c$ ($0 \leq c \leq 10^{18}$),

• N $i$ – information that the $i$-th river flowing north changes its state, i.e., if it was clean, it becomes polluted and vice versa ($1 \leq i \leq n$),

• M $i$ – information that the $i$-th river flowing east changes its state ($1 \leq i \leq m$).

Output

For each query of type Z from the input, output in a separate line one integer, denoting the maximum number of cities to which water can be supplied.

Explanation of Sample

The figure below illustrates the situation before the operations were performed. The solid lines indicate clean rivers, while the dashed lines indicate polluted rivers. There are 12 cities at the intersections of these lines.

The answer for the first query (Z 1) is $11$ because the costs of of bringing water to cities $(1,4)$ and $(2,4)$ are equal to $1$ (hence one of them must remain without access to water), and the costs of bringing water to the other ten cities is equal to $0$.

After executing the second operation (M 1), cities $(1,1)$ and $(2,1)$ lose direct access to the river, similarly after the third and fourth actions only four cities have direct access to the river cities. Thus, the answer to the next query (Z 7) is $9$, because within a budget of $7$ four more cities can be given access to water lying on the straight line $x = 2$ and one city lying on the straight line $x = 1$.

Scoring

The tests are divided into the following subtasks. The tests for each subtask consist of one or more separate test groups.

3 4 11
--+
+++-
Z 1
M 1
M 2
M 3
Z 7
N 3
Z 1000000000000000000
M 2
N 2
Z 4
Z 1000000000000000000

11
9
0
10
12