In Byteland, there are $n$ rivers flowing from south to north along the lines $x = i$ (for $i = 1, 2, \dots, n$) and $m$ rivers flowing from west to east along the lines $y = j$ (for $j = 1, 2, \dots, m$). At every intersection of these rivers, there is a city. In each city, one river flows through a tunnel and does not mix with the other. In the past, every city drew water from the rivers it was located on. Unfortunately, nowadays some rivers are polluted to a degree that makes water treatment impossible, so cities must supply water from other rivers. The cost of supplying water from a river to a city is equal to the distance from the city to the line along which the river flows. Trucks traveling on two-way roads located along the rivers are used to transport water (it does not matter in which direction the river flows, nor from which river the water is delivered to the city).

Unfortunately, Byteland has a limited budget and may not be able to supply water to all cities. The situation is complicated by the fact that some rivers are cleaned, and some are re-polluted. Write a program that reads the current state of the rivers and allows performing two types of actions: changing the state of a river and answering a query about the maximum number of cities that can be supplied with water given a budget.

Input

The first line of the input contains three integers $n, m, z$ ($1 \le n, m, z \le 100\,000$) denoting, respectively: the number of rivers flowing north, the number of rivers flowing east, and the number of actions to process.

The second line contains a string of length $n$ consisting of the characters + and -; the $i$-th character denotes the state of the $i$-th river flowing north: a plus sign means the river is clean, and a minus sign means it is polluted.

The third line contains a string of length $m$ describing the initial state of the rivers flowing east, in an analogous format.

The next $z$ lines contain descriptions of actions in one of the following formats: Z c – a query for the maximum number of cities that can be supplied with water given a budget $c$ ($0 \le c \le 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 \le i \le n$), * M i – information that the $i$-th river flowing east changes its state ($1 \le i \le m$).

Output

For each query of type Z from the input, print one integer in a separate line, representing the maximum number of cities that can be supplied with water.

Examples

Input 1

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

Output 1

11
9
0
10
12

Note

The following figure illustrates the situation before performing any actions. Solid lines represent clean rivers, and dashed lines represent polluted rivers. There are 12 cities at the intersections of these lines.

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

After performing the second action (M 1), cities $(1, 1)$ and $(2, 1)$ lose direct access to a river; similarly, after performing the third and fourth actions, only four cities have direct access to a river. Therefore, the answer to the next query (Z 7) is 9, because within the budget of 7, it is possible to provide water access to four more cities located on the line $x = 2$ and one city located on the line $x = 1$.

Subtasks