After the discovery of Byteland in the year 1024, the continent was divided into $n$ states, and the states were numbered with natural numbers from 1 to $n$. States with higher numbers were from the beginning bastions of conservative thought, while states with lower numbers were inhabited by progressives. In this task, we consider a certain initial period of Byteland's history.

Initially, all states were independent countries, and the state with number $i$ had $i$ stars on its flag. Countries sometimes merged into unions, forming larger countries, and sometimes they underwent breakups. If several states formed a single country at a given moment, its flag contained the total number of stars that were on the flags of the individual member states. A breakup of a country always consisted of dividing the country into a more conservative part and a more progressive part.

Your task is to write a program that analyzes the unions and breakups in the history of Byteland and answers questions regarding the flags of individual countries at given moments in history.

Input

The first line of the input contains three integers $n$, $m$, and $q$ ($1 \le n, m, q \le 100\,000$), representing the number of states in Byteland, the number of historical events, and the number of queries about the flags, respectively.

The next $m$ lines contain the descriptions of historical events in chronological order. The description of the $i$-th event starts with the number $y_i$ ($1024 \le y_i \le 10^6$, $y_1 < y_2 < \dots < y_m$), representing the year in which the $i$-th event took place. The next part of the event description is a single letter $t_i \in \{U, S\}$.

• If $t_i = U$, the rest of the line contains two integers $a_i, b_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i$). This description means that a merger occurred between the country containing state $a_i$ and the country containing state $b_i$. It can be assumed that immediately before this event, states $a_i$ and $b_i$ were not part of the same country.
• If $t_i = S$, the rest of the line contains two integers $a_i, k_i$ ($1 \le a_i, k_i \le n$). This description means that a breakup of the country $P$ containing state $a_i$ occurred into two (non-empty) countries $P_1$ and $P_2$. Country $P_1$ consisted of the states previously belonging to $P$ with numbers smaller than $k_i$, and country $P_2$ consisted of those with numbers greater than or equal to $k_i$.

The next $q$ lines contain descriptions of subsequent queries regarding the flags at various moments in the history of Byteland: the $i$-th of these lines contains two integers $x_i, c_i$ ($1024 \le x_i \le 10^6$, $1 \le c_i \le n$), meaning we are asking for the number of stars on the flag of the country that contained state $c_i$ in the year $x_i$.

We have $x_1 < x_2 < \dots < x_q$ and additionally for any $i, j$ such that $i \in [1, m]$ and $j \in [1, q]$, we have $y_i \neq x_j$.

Output

The output should contain $q$ lines. The $i$-th line should contain a single integer, which is the answer to the $i$-th query from the input.

Examples

Input 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

Output 1

1
7
6
4