사다리 갱신

사다리 게임은 한국뿐 아니라 중국과 일본에서도 널리 하는 게임이다. 위키백과에 따르면 한국에서는 사다리타기, 일본에서는 아미다쿠지(阿弥陀籤, "아미다 제비"), 중국에서는 구이자오투(鬼腳圖, "귀신 다리 그림")라고 부른다.

사다리 판은 $n$개의 세로선으로 이루어지며, 인접한 세로선은 가로줄로 이어진다. 각 세로선에는 위쪽 시작점과 아래쪽 끝점이 있다. 규칙은 간단하다.

• 세로선의 시작점에서 출발해 아래로 내려간다. 가로줄을 만나면 그 가로줄을 따라 옆 세로선으로 이동한 뒤, 세로선의 끝에 도달할 때까지 계속 내려간다.

세로선은 왼쪽부터 $1$번에서 $n$번까지 번호가 매겨진다. 게임 결과는 $\[1, 2, \dots, n]$의 순열이다. 아래 그림은 세로선 $4$개와 가로줄 $5$개로 이루어져 있으며, 결과는 왼쪽부터 $\[2, 3, 4, 1]$이다.

가로줄 중에는 없어도 되는 것이 있다. 가로줄이 더 적어도 같은 결과 $\[2, 3, 4, 1]$을 얻을 수 있다. 아래 그림에서는 맨 위와 맨 아래 가로줄을 제외하면 가로줄 $3$개만으로 같은 결과가 나온다. 같은 결과를 내는 가로줄의 최소 개수를 구한다. 필요하면 새 가로줄을 그려도 된다.

$q$개의 질의가 주어진다. 각 질의는 가로줄을 추가하거나 기존 가로줄을 삭제한다. 질의는 누적되므로, 각 질의는 이전 질의까지 반영된 사다리에 적용된다. 각 질의를 처리한 뒤의 사다리와 같은 결과를 내는 가로줄의 최소 개수를 구한다.

첫 줄에 세 정수 $n$, $m$, $q$가 공백으로 구분되어 주어진다. $2 \le n \le 100\,000$, $1 \le m \le 100\,000$, $1 \le q \le 100\,000$이다.

다음 $m$개의 줄에는 두 양의 정수 $h$와 $a$가 주어진다. 이는 높이 $h$에서 $a$번째 세로선과 $a + 1$번째 세로선을 잇는 가로줄이 있다는 뜻이다. 단, $1 \le a \le n - 1$이다. 높이는 위에서 아래로 $1$부터 번호가 매겨지며, $h \le 10^9$이다.

다음 $q$개의 줄에는 질의가 주어진다. 질의는 A $h$ $a$ 또는 D $h$ $a$의 형태이며, $1 \le h \le 10^9$, $1 \le a \le n - 1$이다.

• A $h$ $a$: 높이 $h$에서 $a$번째와 $a + 1$번째 세로선 사이에 가로줄을 추가한다.
• D $h$ $a$: 높이 $h$에서 $a$번째와 $a + 1$번째 세로선 사이의 가로줄을 삭제한다.

모순되는 연산은 주어지지 않는다. 이미 있는 가로줄을 다시 추가하지 않고, 없는 가로줄을 삭제하지 않는다. 또한 같은 세로선의 같은 높이에 있는 끝점을 공유하는 두 가로줄은 없다.

$q$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 질의를 처리한 뒤의 사다리와 같은 게임 결과를 내는 가로줄의 최소 개수를 출력한다.