사다리 게임은 한국뿐 아니라 중국과 일본에서도 인기 있는 게임이다. Wikipedia에 따르면 “한국어로는 Sadaritagi(사다리타기, 문자 그대로 ‘사다리 오르기’), 일본어로는 Amidakuji(阿弥陀籤, ‘아미타 추첨’), 중국어로는 Guijiaotu(鬼腳圖, 문자 그대로 ‘귀신 다리 그림’)라고 알려져 있다.”

게임을 하는 도식은 $n$개의 수직선과 인접한 두 수직선을 연결하는 수평 선분으로 이루어진다. 수평 선분을 다리라고 한다. 각 수직선에는 시작점(위쪽)과 끝점(아래쪽)이 있다. 기본 규칙은 다음과 같이 간단하다.

• 각 수직선의 시작점에서 출발하여 수직선을 따라 내려간다. 다리를 만나면 그 다리를 따라 인접한 수직선으로 이동하고, 수직선의 끝점에 도달할 때까지 계속 내려간다.

수직선에는 왼쪽부터 오른쪽으로 $1$부터 $n$까지 번호가 붙어 있다. 게임 결과가 $[1,2,\ldots,n]$의 순열이 된다는 것은 잘 알려져 있다. 예를 들어 아래의 수직선 4개와 다리 5개로 된 도식에서, 왼쪽부터 게임 결과는 $[2,3,4,1]$이다.

하지만 일부 다리는 불필요하다. 즉, 더 적은 다리로 같은 결과 $[2,3,4,1]$을 얻을 수 있다. 아래 그림처럼 맨 위와 맨 아래의 다리를 제외한 세 다리만으로 같은 결과를 얻는다. 같은 결과를 얻는 데 필요한 수평 선분(다리)의 최소 개수를 구하고 싶다. 필요하다면 주어진 것과 다른 새로운 다리를 그려도 된다.

$q$개의 쿼리가 주어지며, 각각 새 다리를 추가하거나 기존 다리를 삭제한다. 각 쿼리를 처리한 뒤 얻은 사다리 구조와 같은 게임 결과를 얻는 데 필요한 최소 다리 수를 출력하는 프로그램을 작성하라. 쿼리는 누적되며, 다음 쿼리는 이전 쿼리들의 결과로 생긴 사다리 구조에 적용된다.

입력

프로그램은 표준 입력에서 읽어야 한다. 첫 줄에는 수직선 수 $n$, 초기 다리 수 $m$, 쿼리 수 $q$가 공백으로 구분되어 주어진다. $2\le n\le100000$, $1\le m\le100000$, $1\le q\le100000$이다.

다음 $m$개의 줄에는 각각 두 양의 정수 $h,a$가 주어진다. 이는 높이 $h$에서 $a$번째와 $(a+1)$번째 수직선을 연결하는 다리를 나타낸다($1\le a\le n-1$). 수직선은 왼쪽에서 오른쪽 순서이고, 높이는 위에서 아래로 $1$부터 번호를 매긴다. 높이는 $10^9$ 이하이다.

다음 $q$개의 줄에는 쿼리가 주어진다. 각 쿼리는 $\mathrm{A}\ h\ a$ 또는 $\mathrm{D}\ h\ a$ 형식이다($1\le h\le10^9$, $1\le a\le n-1$).

• $\mathrm{A}\ h\ a$: 높이 $h$에 $a$번째와 $(a+1)$번째 수직선 사이의 다리를 추가한다.

• $\mathrm{D}\ h\ a$: 높이 $h$의 $a$번째와 $(a+1)$번째 수직선 사이의 다리를 삭제한다.

모순된 연산은 없다고 가정해도 된다. 즉, 이미 존재하는 다리를 추가하거나 존재하지 않는 다리를 삭제하지 않는다. 또한 같은 높이와 같은 수직선의 끝점을 공유하는 두 다리는 없다고 가정해도 된다.

출력

프로그램은 표준 출력에 써야 한다. 출력은 $q$개의 줄로 이루어지며, 각 줄에는 입력 순서대로 해당 쿼리와 같은 결과를 얻는 데 필요한 최소 다리 수를 출력한다.

다음은 두 테스트 케이스의 예제 입력과 출력을 보여준다.

예제

입력 1

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

출력 1

3
6
3

참고

예제 입력 1은 아래 초기 사다리 구조를 준다. 게임 결과는 $[3,2,4,1]$이다.

아래 그림에서 첫 쿼리 A 7 1을 적용하면 사다리 구조가 바뀌고 결과는 $[2,3,4,1]$이 된다.

아래 그림처럼 다섯 다리 중 맨 위와 맨 아래를 제외한 세 다리만으로 같은 결과 $[2,3,4,1]$을 얻을 수 있으므로 첫 번째 쿼리의 답은 $3$이다.

두 번째 쿼리 A 4 3을 처리하면 사다리 구조가 아래와 같이 바뀐다. 다리 수를 더 줄일 수 없다. 두 번째 쿼리의 답은 $6$이다.

세 번째 쿼리 D 3 1을 적용하면 사다리 구조가 아래와 같이 바뀐다.

아래의 세 다리로 된 사다리 구조는 같은 게임 결과를 보장하므로 세 번째 쿼리의 답은 $3$이다.

입력 2

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

2
3
2
1
0