梯子ゲームは韓国だけでなく中国と日本でも人気があります。Wikipedia によると「韓国語では Sadaritagi（사다리타기、文字どおり『梯子登り』）、日本語では Amidakuji（阿弥陀籤、『阿弥陀のくじ』）、中国語では Guijiaotu（鬼腳圖、文字どおり『幽霊の脚の図』）として知られています。」

ゲームを行う図は $n$ 本の縦線と、隣り合う 2 本の縦線を結ぶ横線分からなります。この横線分を脚と呼びます。各縦線には始点（上側）と終点（下側）があります。基本規則は次のように簡単です。

• 各縦線の始点から縦線に沿って下へ進みます。脚に出会うとそれに沿って隣の縦線へ移動し、縦線の終点に達するまで下へ進み続けます。

縦線には左から右へ $1$ から $n$ と番号が付いています。結果が $[1,2,\ldots,n]$ の順列になることはよく知られています。例えば下の縦線 4 本、脚 5 本の図では、左から右への結果は $[2,3,4,1]$ です。

ただし一部の脚は冗長で、より少ない脚でも同じ結果 $[2,3,4,1]$ が得られます。下の図のように、一番上と一番下の脚を除く 3 本だけで同じ結果が得られます。同じ結果を得るために必要な横線分（脚）の最小本数を求めたいと思います。必要なら、与えられたものとは異なる新しい脚を描いてもかまいません。

$q$ 個のクエリが与えられ、それぞれ新しい脚を追加するか既存の脚を削除します。各クエリ処理後の梯子構造と同じ結果を得るために必要な脚の最小本数を出力するプログラムを書いてください。クエリは累積的であり、各クエリはそれまでのクエリで得られた構造に適用されます。

入力

プログラムは標準入力から読み込みます。最初の行には、縦線の本数 $n$、初期の脚の本数 $m$、クエリ数 $q$ が空白区切りで与えられます。$2\le n\le100000$、$1\le m\le100000$、$1\le q\le100000$ です。

続く $m$ 行の各行には 2 つの正の整数 $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)$ 本目の縦線を結ぶ脚を削除します。

矛盾する操作はなく、存在する脚が追加されたり、存在しない脚が削除されたりすることはありません。また、同じ高さの同じ縦線上の端点を共有する 2 本の脚はないと仮定できます。

出力

プログラムは標準出力へ書き込みます。出力は $q$ 行で、入力順に各クエリと同じ結果を得るために必要な脚の最小本数を出力してください。

以下に 2 つのテストケースの入力例と出力例を示します。

入出力例

入力 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]$ になります。

下の図のように、5 本の脚のうち一番上と一番下を除く 3 本だけで同じ結果 $[2,3,4,1]$ が得られるので、最初のクエリの答えは $3$ です。

2 番目のクエリ A 4 3 を処理すると下の構造になります。脚の本数をこれ以上減らすことはできません。2 番目の答えは $6$ です。

3 番目のクエリ D 3 1 を適用すると下の構造になります。

下の脚が 3 本の構造は同じ結果を保証するので、3 番目のクエリの答えは $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