[AdditionalFile5639.zip](file://AdditionalFile5639.zip?type=additional_file)

#5639. 「PA 2015 Final」Stany

标签: 传统 | 时间限制: 10000 ms | 内存限制: 256 MiB |

题目描述

题目译自 PA 2015 Final Stany

自 $1024$ 年发现 Bajtyka 大陆后，该大陆被划分为 $n$ 个联邦州，这些联邦州按自然数 $1$ 到 $n$ 依次编号。从一开始，编号较大的州就是保守派思想的堡垒，而编号较小的州则居住着进步人士。在本题中，我们研究 Bajtyka 历史上的一个初始阶段。

最初，所有州都是独立的国家，编号为 $i$ 的州在其旗帜上有 $i$ 颗星星。这些国家有时会合并成联邦，形成更大的国家，有时则会经历解体。如果在某个时刻，若干个州组成了一个国家，那么该国旗帜上的星星数量等于其所有成员州旗帜上星星数量的总和。国家的解体总是表现为将国家划分为一个更保守的部分和一个更进步的部分。

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

输入格式

输入的第一行包含三个整数 $n, m$ 和 $q$ $(1 \leq n, m, q \leq 100000)$，分别表示拜泰卡的州数、历史事件的数量以及关于旗帜的询问数量。

接下来的 $m$ 行按时间先后顺序描述历史事件。第 $i$ 个事件的描述以年份 $y_{i}$ $(1024 \leq y_{i} \leq 10^{6}, y_{1}<y_{2}<\ldots<y_{m})$ 开头。事件描述的下一部分是一个字母 $t_{i} \in\{\texttt{U}, \texttt{S}\}$。

• 如果 $t_{i}=\texttt{U}$，则该行的其余部分包含两个整数 $a_{i}, b_{i}$ $(1 \leq a_{i}, b_{i} \leq n, a_{i} \neq b_{i})$。这一描述表示包含州 $a_{i}$ 的国家与包含州 $b_{i}$ 的国家发生了合并。可以假设在此事件发生前，州 $a_{i}$ 和州 $b_{i}$ 不属于同一个国家。
• 如果 $t_{i}=\texttt{S}$，则该行的其余部分包含两个整数 $a_{i}, k_{i}$ $(1 \leq a_{i}, k_{i} \leq n)$。这一描述表示包含州 $a_{i}$ 的国家 $P$ 解体为两个（非空）国家 $P_{1}$ 和 $P_{2}$。原属于 $P$ 且编号小于 $k_{i}$ 的州划归国家 $P_{1}$，而编号大于或等于 $k_{i}$ 的州划归国家 $P_{2}$。

接下来的 $q$ 行描述了关于拜泰卡不同历史时期旗帜的询问：第 $i$ 行包含两个整数 $x_{i}, c_{i}$ $(1024 \leq x_{i} \leq 10^{6}, 1 \leq c_{i} \leq n)$，表示询问在 $x_{i}$ 年包含州 $c_{i}$ 的国家旗帜上的星星数量。满足 $x_{1}<x_{2}<\ldots<x_{q}$，且对于所有的 $i \in [1, m]$ 和 $j \in [1, q]$，均有 $y_{i} \neq x_{j}$。

输出格式

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

样例

输入

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
7
6
4