梯子游戏（Ladder game）在韩国、中国和日本都很流行。维基百科称：“它在韩国被称为 Sadaritagi（사다리타기，字面意思是“爬梯子”），在日语中被称为 Amidakuji（阿弥陀籤，意为“阿弥陀佛抽签”），在中文中被称为鬼脚图（Guijiaotu，字面意思是“鬼脚图”）。”

游戏所在的图由 $n$ 条垂直线和连接两条相邻垂直线的水平线段组成。这些水平线段被称为“横木”（legs）。每条垂直线都有一个起点（上端）和一个终点（下端）。该游戏的基本规则如下：

• 从每条垂直线的起点出发，沿垂直线向下移动。当遇到横木时，沿横木移动到相邻的垂直线，并继续向下，直到到达垂直线的终点。

垂直线从左到右编号为 $1$ 到 $n$。众所周知，游戏结果是 $[1, 2, \dots, n]$ 的一个排列。例如，给定一个有 $4$ 条垂直线和 $5$ 根横木的图（如下图所示），游戏结果从左到右为 $[2, 3, 4, 1]$。

然而，有些横木是多余的，这意味着同样的 $[2, 3, 4, 1]$ 结果可以用更少的横木实现；如下图所示，仅需排除最上方和最下方的横木，用三根横木即可获得相同的结果。我们希望确定实现相同结果所需的最少横木数量。注意，如有必要，可以绘制与给定横木不同的新横木。

给定 $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$ 开始。高度不超过 $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$ 行，每行包含按输入顺序处理每个查询后，实现相同结果所需的最少横木数量。

样例

输入 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

输入 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

说明

样例输入 1 的解释：

样例输入 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。

图 1. 一个有 4 条垂直线和 5 根横木的图