問題文

長さ $N$ の数列 $P_1, P_2, \dots, P_N$ と $N$ 個の文字列 $S_1, S_2, \dots, S_N$ が与えられます。ただし、$S_i$ ($1 \leq i \leq N)$ は AC または WA です。

$Q$ 個のクエリが与えられるので、処理してください。

高橋くんは $M$ 問の問題からなるプログラミングコンテストに参加し、コンテスト中に $R_i-L_i+1$ 回の提出を行いました。

$j$ 回目 ($1 \leq j \leq R_i-L_i+1$) の提出は $P_{L_i+j-1}$ 番目の問題への提出であり、結果は $S_{L_i+j-1}$ です。

高橋くんの正答数は、AC を $1$ 回以上出した問題の個数です。

高橋くんのペナルティ数は、AC を $1$ 回以上出した各問題に対する、最初の AC 提出の前の WA 提出の個数の総和です。

高橋くんの正答数とペナルティ数を求めてください。

入力

入力は以下の形式で標準入力から与えられます。

$N$ $M$ $Q$
$P_1$ $S_1$
$P_2$ $S_2$
$\vdots$
$P_N$ $S_N$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_Q$ $R_Q$

出力

標準出力に $Q$ 行出力してください。$i$ 行目 ($1 \leq i \leq Q$) には、クエリ $i$ での高橋くんの正答数とペナルティ数をこの順に空白区切りで出力してください。
最後に改行してください。

制約

入力は以下の制約を満たします。

• $1 \leq N \leq 200\,000$
• $1 \leq M \leq 200\,000$
• $1 \leq Q \leq 200\,000$
• $1 \leq P_i \leq M$ ($1 \leq i \leq N)$
• $S_i$ ($1 \leq i \leq N$) は AC または WA である。
• $1 \leq L_i \leq R_i \leq N$ ($1 \leq i \leq Q)$
• $N,M,Q,P_i,L_i,R_i$ はすべて整数である。

サンプル

5 5 5
3 WA
3 AC
2 AC
5 WA
2 WA
1 2
3 3
2 4
2 5
1 5

1 1
1 0
2 0
2 0
2 1