题目描述

有两个相邻的围栏区域：一个区域中生活着一群猪，另一个区域中生活着一群长颈鹿。

猪不能进入长颈鹿所在的区域，长颈鹿也不能进入猪所在的区域，但它们可以隔着围栏交谈。猪只愿意直接与长颈鹿交谈，长颈鹿也只愿意直接与猪交谈。

这种关系是相互的：如果某只猪愿意与某只长颈鹿交谈，那么这只长颈鹿也愿意与这只猪交谈。任何两只猪之间都不存在直接交谈关系，任何两只长颈鹿之间也不存在直接交谈关系。

即使两只动物不愿意直接交谈，它们仍可以让消息经过其他动物转发。消息只能在彼此愿意直接交谈的动物之间传递。

定义两只动物之间的噪声等级为：把一条消息从其中一只动物传到另一只动物，最少需要经过多少次直接交谈。

• 如果两只动物愿意直接交谈，则它们之间的噪声等级为 $1$；
• 如果消息需要经过一只中间动物，则噪声等级为 $2$；
• 依此类推；
• 如果两只动物之间无法传递消息，则它们之间的噪声等级定义为 $0$。

定义整个动物群体的总噪声等级为：所有不同动物的无序对之间的噪声等级之和。每一对动物只计算一次。

动物的数量会不断增加。每只新生动物由两只已经存在的、种类相同的动物作为亲本：

• 两只亲本都是猪时，新生动物也是猪；
• 两只亲本都是长颈鹿时，新生动物也是长颈鹿。

新生动物一出生就可以与其他动物交谈。

对于任意一只现有动物，如果它恰好只与两个亲本中的一个存在直接交谈关系，那么新生动物就愿意与它交谈；如果它同时与两个亲本交谈，或与两个亲本都不交谈，则新生动物不与它交谈。

换句话说，新生动物的邻居集合等于两个亲本邻居集合的对称差。

给定初始动物及其交谈关系，以及一系列新动物出生事件。每次有新动物出生后，请计算当前的总噪声等级。

输入格式

第一行包含三个整数 $A,B,M$：

其中：

• $A$ 表示初始猪的数量；
• $B$ 表示初始长颈鹿的数量；
• $M$ 表示初始时存在直接交谈关系的猪—长颈鹿对数。

初始的猪编号为 $0,1,\ldots,A-1$，初始的长颈鹿编号为 $0,1,\ldots,B-1$。

接下来 $M$ 行，每行包含两个整数 $a,b$（$0\le a<A$，$0\le b<B$），表示编号为 $a$ 的猪与编号为 $b$ 的长颈鹿愿意直接交谈。

下一行包含一个整数 $Q$（$1\le Q\le 10^5$），表示将要出生的新动物数量。

接下来 $Q$ 行，每行描述一只新生动物，格式为：

X p q

其中：

• X 为 A 或 B；
• X = A 表示新生动物是一只猪；
• X = B 表示新生动物是一只长颈鹿；
• $p,q$ 是它的两只亲本编号。

两只亲本一定已经存在，并且与新生动物属于同一种类。

每个种类内部独立编号。新生动物获得该种类中当前最小的未使用编号；等价地，它的编号就是该种类在出生前已有动物的数量。

输出格式

输出 $Q$ 行。

第 $i$ 行输出第 $i$ 只新动物出生后，当前所有动物的总噪声等级。

样例 1

输入

4 4 4
0 0
1 1
2 2
3 3
2
A 0 1
A 0 1

输出

22
30

样例 2

输入

3 3 5
0 0
1 0
1 1
2 1
2 2
3
B 0 1
B 3 2
B 3 4

输出

42
61
82

图示

下图表示样例 2 的全部出生事件处理完成后的关系图。上方为长颈鹿，下方为猪，连线表示双方愿意直接交谈。