Gra w drabinę jest popularna w Korei, a także w Chinach i Japonii. Wikipedia podaje: „Po koreańsku znana jest jako Sadaritagi (사다리타기, dosłownie «wspinanie się po drabinie»), po japońsku jako Amidakuji (阿弥陀籤, «loteria Amidy»), a po chińsku jako Guijiaotu (鬼腳圖, dosłownie «diagram nóg ducha»).”

Diagram gry składa się z $n$ pionowych linii i poziomych odcinków łączących dwie sąsiednie pionowe linie. Poziome odcinki nazywamy szczeblami. Każda pionowa linia ma punkt początkowy (górny) i końcowy (dolny). Podstawowa zasada gry jest prosta:

• Zacznij w punkcie początkowym każdej pionowej linii i poruszaj się po niej w dół. Po napotkaniu szczebla przejdź po nim do sąsiedniej linii i kontynuuj w dół aż do punktu końcowego pionowej linii.

Pionowe linie są ponumerowane od $1$ do $n$ od lewej do prawej. Wiadomo, że wynik gry jest permutacją $[1,2,\ldots,n]$. Na przykład dla diagramu poniżej, z 4 pionowymi liniami i 5 szczeblami, wynik od lewej do prawej wynosi $[2,3,4,1]$.

Niektóre szczeble są jednak zbędne: ten sam wynik $[2,3,4,1]$ można otrzymać przy mniejszej liczbie szczebli. Jak na poniższym rysunku, wystarczą trzy szczeble po pominięciu najwyższego i najniższego. Chcemy ustalić minimalną liczbę poziomych odcinków (szczebli) potrzebną do uzyskania tego samego wyniku. W razie potrzeby można narysować nowe szczeble, inne niż podane.

Danych jest $q$ zapytań, z których każde dodaje nowy szczebel albo usuwa istniejący. Napisz program wypisujący minimalną liczbę szczebli potrzebną do uzyskania tego samego wyniku co struktura drabiny po przetworzeniu zapytania. Zapytania kumulują się: każde kolejne stosuje się do struktury otrzymanej po poprzednich zapytaniach.

Wejście

Program ma czytać ze standardowego wejścia. Pierwszy wiersz zawiera trzy liczby całkowite oddzielone spacją: liczbę pionowych linii $n$, początkową liczbę szczebli $m$ i liczbę zapytań $q$, gdzie $2\le n\le100000$, $1\le m\le100000$, $1\le q\le100000$.

Każdy z kolejnych $m$ wierszy zawiera dwie dodatnie liczby całkowite $h,a$, oznaczające szczebel na wysokości $h$ łączący $a$-tą i $(a+1)$-szą pionową linię ($1\le a\le n-1$). Pionowe linie są uporządkowane od lewej do prawej, a wysokość jest numerowana od góry do dołu od $1$. Wysokość nie przekracza $10^9$.

Kolejnych $q$ wierszy zawiera zapytania. Każde ma postać $\mathrm{A}\ h\ a$ albo $\mathrm{D}\ h\ a$, gdzie $1\le h\le10^9$, $1\le a\le n-1$.

• $\mathrm{A}\ h\ a$: dodaj szczebel na wysokości $h$ pomiędzy $a$-tą i $(a+1)$-szą pionową linią.

• $\mathrm{D}\ h\ a$: usuń szczebel na wysokości $h$ pomiędzy $a$-tą i $(a+1)$-szą pionową linią.

Możesz założyć brak sprzecznych operacji: istniejące szczeble nie będą dodawane, a nieistniejące usuwane. Możesz też założyć, że żadne dwa szczeble nie mają wspólnego końca na tej samej wysokości na tej samej pionowej linii.

Wyjście

Program ma pisać na standardowe wyjście. Wyjście składa się z $q$ wierszy; każdy zawiera minimalną liczbę szczebli potrzebną do uzyskania tego samego wyniku dla zapytania, w kolejności wejściowej.

Poniżej przedstawiono przykładowe wejście i wyjście dla dwóch przypadków testowych.

Przykład

Wejście 1

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

Wyjście 1

3
6
3

Uwagi

Pierwszy przykład daje poniższą początkową strukturę drabiny. Wynik wynosi $[3,2,4,1]$.

Po zastosowaniu pierwszego zapytania A 7 1 na poniższym rysunku struktura zmienia się, a wynik to $[2,3,4,1]$.

Spośród pięciu szczebli wystarczą trzy, bez najwyższego i najniższego, aby uzyskać ten sam wynik $[2,3,4,1]$, jak na rysunku poniżej. Odpowiedź na pierwsze zapytanie wynosi więc $3$.

Po przetworzeniu drugiego zapytania A 4 3 struktura zmienia się jak poniżej. Liczby szczebli nie można już zmniejszyć. Odpowiedź na drugie zapytanie wynosi $6$.

Po zastosowaniu trzeciego zapytania D 3 1 struktura zmienia się jak poniżej.

Poniższa struktura z trzema szczeblami zapewnia ten sam wynik, więc odpowiedź na trzecie zapytanie wynosi $3$.

Wejście 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

Wyjście 2

2
3
2
1
0