Problem Statement

You are given a sequence $P_1, P_2, \dots, P_N$ of length $N$ and $N$ strings $S_1, S_2, \dots, S_N$. Here, $S_i$ ($1 \leq i \leq N)$ is AC or WA.

You are given $Q$ queries; process them.

Takahashi participated in a programming contest consisting of $M$ problems and made $R_i-L_i+1$ submissions during the contest.

The $j$-th submission ($1 \leq j \leq R_i-L_i+1$) was made to problem $P_{L_i+j-1}$, and its result was $S_{L_i+j-1}$.

Takahashi's number of correct answers is the number of problems for which he got AC at least $1$ time.

Takahashi's number of penalties is the sum, over all problems for which he got AC at least $1$ time, of the number of WA submissions before the first AC submission to that problem.

Find Takahashi's number of correct answers and number of penalties.

Input

The input is given from Standard Input in the following format.

$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$

Output

Print $Q$ lines to Standard Output. On the $i$-th line ($1 \leq i \leq Q$), print Takahashi's number of correct answers and number of penalties for query $i$, in this order, separated by a space.
End the output with a newline.

Constraints

The input satisfies the following constraints.

• $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$) is AC or WA.
• $1 \leq L_i \leq R_i \leq N$ ($1 \leq i \leq Q)$
• $N,M,Q,P_i,L_i,R_i$ are all integers.

Sample

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