自 1024 年发现 Bajtyka 以来，该大陆被划分为 $n$ 个州，各州按自然数从 1 到 $n$ 编号。编号较大的州从一开始就是保守派思想的堡垒，而编号较小的州则居住着进步派。在本题中，我们考虑 Bajtyka 历史上的一个初始时期。

起初，所有州都是独立的国家，编号为 $i$ 的州在其旗帜上有 $i$ 颗星。国家有时会合并成更大的国家，有时会发生分裂。如果若干个州在某一时刻组成了一个国家，那么该国家的旗帜上的星数等于其各成员州旗帜上的星数之和。国家的分裂总是表现为将国家划分为一个更保守的部分和一个更进步的部分。

你的任务是编写一个程序，分析 Bajtyka 历史上的合并与分裂，并回答关于历史特定时刻各国家旗帜的问题。

输入格式

输入的第一行包含三个整数 $n, m, q$ ($1 \le n, m, q \le 100\,000$)，分别表示 Bajtyka 的州数、历史事件数以及关于旗帜的查询数。

接下来的 $m$ 行按时间顺序描述了历史事件。第 $i$ 个事件的描述以年份 $y_i$ ($1024 \le y_i \le 10^6, y_1 < y_2 < \dots < y_m$) 开头，表示该事件发生的年份。描述的下一部分是一个字符 $t_i \in \{U, S\}$。

• 如果 $t_i = U$，则该行后续包含两个整数 $a_i, b_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i$)。这表示包含州 $a_i$ 的国家与包含州 $b_i$ 的国家发生了合并。可以假设在该事件发生前，州 $a_i$ 和 $b_i$ 不属于同一个国家。
• 如果 $t_i = S$，则该行后续包含两个整数 $a_i, k_i$ ($1 \le a_i, k_i \le n$)。这表示包含州 $a_i$ 的国家 $P$ 分裂为两个（非空）国家 $P_1$ 和 $P_2$。国家 $P_1$ 包含原先属于 $P$ 且编号小于 $k_i$ 的州，国家 $P_2$ 包含原先属于 $P$ 且编号大于或等于 $k_i$ 的州。

接下来的 $q$ 行描述了关于 Bajtyka 历史特定时刻旗帜的查询：第 $i$ 行包含两个整数 $x_i, c_i$ ($1024 \le x_i \le 10^6, 1 \le c_i \le n$)，表示查询在 $x_i$ 年包含州 $c_i$ 的国家的旗帜上的星数。

已知 $x_1 < x_2 < \dots < x_q$，且对于任意 $i \in [1, m]$ 和 $j \in [1, q]$，满足 $y_i \neq x_j$。

输出格式

输出 $q$ 行。第 $i$ 行应包含一个整数，即对输入中第 $i$ 个查询的回答。

样例

输入 1

4 4 4
1025 U 1 2
1030 U 4 1
2015 S 4 2
2018 U 1 3
1024 1
1031 2
2016 4
2020 3

输出 1

1
7
6
4