Ladder Update

문제

Ladder game is a popular game in Korea, as well as China and Japan. Wikipedia says that “It is known in Korean as Sadaritagi (사다리타기, literally "ladder climbing"), in Japanese as Amidakuji (阿弥陀籤, "Amida lottery"), and in Chinese as Guijiaotu (鬼腳圖, literally "ghost leg diagram").”

The diagram where the game is played consists of $nn$ vertical lines with horizontal line segments connecting two adjacent vertical lines. The horizontal line segments are called legs. Each vertical line has a starting (upper) point and an end (lower) point. The basic rule of this game is simple as follows:

• Start from the starting point of each vertical line and move downward along the vertical line. When encountering a leg, move along the leg to the adjacent vertical line, and continue downwards until reaching the end of a vertical line.

The vertical lines are numbered from $11$ to $nn$ from left to right. It is well known that the game result is a permutation of $[1,2,\dots ,n][1,\; 2,\; \backslash dots\; ,\; n]$. For example, given a diagram with $44$ vertical lines and $55$ legs shown below, the game result is $[2,3,4,1][2,\; 3,\; 4,\; 1]$ from left to right.

However, some legs are redundant, meaning that the same result $[2,3,4,1][2,\; 3,\; 4,\; 1]$ can be achieved with fewer legs; as in the figure below, one can obtain the same result only with three legs excluding topmost and bottommost ones. We want to determine the minimum number of horizontal line segments (legs) needed to achieve the same result. Note that it is possible to draw new legs than the given ones if necessary.

You are given $qq$ queries, where each query either adds a new leg or deletes an existing one. Write a program to output the minimum number of legs required to achieve the same game result of the ladder structure obtained after the query is processed. Note that each query is cumulative, meaning each subsequent query is applied to the ladder structure resulting from previous queries.

입력

Your program is to read from standard input. The input starts with a line containing three integers $nn$, the number of vertical lines, $mm$, the initial number of legs, and $qq$, the number of queries, separated by a space where 2 ≤ n ≤ 100\,000, 1 ≤ m ≤ 100\,000, and 1 ≤ q ≤ 100\,000.

In the following $mm$ lines, each line contains two positive integers $hh$ and $aa$, representing a leg at height $hh$ connecting the $aa$-th and $(a+1)(a\; +\; 1)$-th vertical lines (1 ≤ a ≤ n - 1). The vertical lines are ordered from left to right, and the height is numbered from top to bottom starting with $11$. The height is no more than ${10}^{9}10^9$.

The next $qq$ lines contain the query information. Each query is either in the form of A $hh$ $aa$ or D $hh$ $aa$, where 1 ≤ h ≤ 10^9, 1 ≤ a ≤ n - 1.

• A $hh$ $aa$: add a leg at height $hh$ between the $aa$-th and $(a+1)(a\; +\; 1)$-th vertical lines.
• D $hh$ $aa$: delete the leg at height $hh$ between the $aa$-th and $(a+1)(a\; +\; 1)$-th vertical lines.

You can assume that there are no contradictory operations, that is, existing legs will not be added, and non-existing legs will not be deleted. Also, you can assume that no two legs are positioned such that they share the endpoint of the same height and the same vertical line.

출력

Your program is to write to standard output. The output consists of $qq$ lines and each line contains the minimum number of legs required to achieve the same result for a query in the input order.

4 4 3
3 1
2 2
5 2
6 3
A 7 1
A 4 3
D 3 1

3
6
3

4 5 5
3 1
2 2
5 2
6 3
7 1
D 6 3
D 7 1
D 5 2
D 3 1
D 2 2

2
3
2
1
0