Little $\Delta$'s string skills have finally reached the level of the popularization group! He learned how to count the occurrences of one string in another, but he realized this is a well-known problem and cannot be used in a mutual-testing contest. A few days later, Little $\Delta$ started learning advanced string algorithms, such as finding the longest palindromic substring, but this is also a well-known problem. However, Little $\Delta$ felt that by simply combining these two problems, it would no longer be a well-known problem. The problem he created is as follows:

For a string $S=a_1a_2a_3\cdots a_k$, define the length of the string as $|S|=k$, define the substring of $S$ at $[l,r]$ as $S[l,r]=a_la_{l+1}\cdots a_{r}$, and define its reverse as $S^R=a_ka_{k-1}\cdots a_1$.

Define the palindrome set of a string $S$ as the set of positions of all palindromic substrings within it, i.e., $P(S)=\{(l,r)\in \mathbb Z^2\mid 1\leq l\leq r\leq |S|, S[l,r]=(S[l,r])^R\}$.

Define two strings $S, T$ as palindrome-matched, denoted as $S\approx T$, if and only if $P(S)=P(T)$.

Given $n$ strings $S_i$, let $f(i,j)$ be the number of substrings of $S_j$ that are palindrome-matched with $S_i$, i.e., $f(i,j)=\left|\{ (l,r) \in \mathbb Z^2\mid 1\leq l\leq r\leq |S_j|, S_j[l,r]\approx S_i\}\right|$.

Given $q$ queries, each providing $i, j$, calculate $f(i,j)$.

There are two input methods for this problem. The first provides $S_i$ directly, and the second defines $S_i$ as a previous string $S_{f_i}$ followed by a character $c_i$. See the Input section for details.

Input

The first line contains three integers $T, n, q$.

If $T=0$, the next $n$ lines each contain a string $S_i$.

If $T=1$, the next $n$ lines each contain an integer $f_i$ and a character $c_i$. If $f_i=0$, it means $S_i=c_i$; otherwise, it means $S_i=S_{f_i}c_i$.

The next $q$ lines each contain two positive integers $i, j$, representing a query.

Output

Output $q$ lines, each containing an integer representing the answer to a query.

Examples

Input 1

0 5 4
aba
acaba
acaca
aa
zzzzz
1 2
1 3
2 3
4 5

Output 1

2
3
0
4

Input 2

0 2 1
abca
jintianshikendejifengkuangxingqisivwowushi
1 2

Output 2

35

Note 2

It is a pity that this problem was not used in the Thursday exam.

Input 3

1 7 4
0 a
1 b
2 a
1 a
4 b
5 a
0 a
7 6
3 6
2 5
4 6

Output 3

4
1
1
1

Constraints

$T\in\{0,1\}, 1\leq n, q\leq 5\times 10^5$, $S_i$ are non-empty and contain only lowercase English letters, $1\leq i, j\leq n$.

When $T=0$, let $L=\sum_{i=1}^n |S_i|$, it is guaranteed that $L\leq 5\times 10^5$.

When $T=1$, it is guaranteed that $0\leq f_i\leq i-1$.

Subtask 1 (5 points): $T=0, L\leq 1000$.

Subtask 2 (15 points): $T=0$, all $|S_i|$ are equal.

Subtask 3 (20 points): $T=0, q=1$.

Subtask 4 (20 points): $T=0$.

Subtask 5 (40 points): No special restrictions.