小 $\Delta$ 的字符串水平终于达到了普及组水平！他学会了求一个字符串在另一个字符串中的出现次数，但他意识到了这是为人熟知的原题，不能出到互测里。过了几天，小 $\Delta$ 开始学习提高组字符串算法，比如求一个字符串的最长回文子串，但这也是为人熟知的原题。但小 $\Delta$ 觉得只需要融合一下这两道题，就不算为人熟知的原题了，他出的题目如下。

对于一个字符串 $S=a_1a_2a_3\cdots a_k$，定义字符串的长度 $\left|S\right|=k$，定义 $S$ 的子串 $[l,r]$ 为 $S[l,r]=a_la_{l+1}\cdots a_{r}$，并定义其反转为 $S^R=a_ka_{k-1}\cdots a_1$

定义一个字符串 $S$ 的回文集合是其中所有回文串的位置的集合，也就是 $P(S)=\{(l,r)\in \mathbb Z^2\mid 1\leq l\leq r\leq \left|S\right|, S[l,r]=(S[l,r])^R\}$

定义两个字符串 $S,T$ 回文匹配，记为 $S\approx T$， 当且仅当 $P(S)=P(T)$

给定 $n$ 个字符串 $S_i$，令 $f(i,j)$ 为 $S_j$ 有多少个子串与 $S_i$ 回文匹配，也就是 $f(i,j)=\left|\{ (l,r) \in \mathbb Z^2\mid 1\leq l\leq r\leq \left|S_j\right|, S_j[l,r]\approx S_i\}\right|$

给定 $q$ 次询问，每次给定 $i,j$，求 $f(i,j)$

本题有两种输入方式，第一种是直接给出 $S_i$，第二种是把 $S_i$ 给定为其前面的某一个 $S_{f_i}$ 后面接上一个字符 $c_i$，见输入格式。

输入格式

第一行，三个整数 $T,n,q$

若 $T=0$，则接下来 $n$ 行，第 $i$ 行一个字符串 $S_i$

若 $T=1$，则接下来 $n$ 行，第 $i$ 行一个整数 $f_i$，和一个字符 $c_i$，若 $f_i=0$，则代表 $S_i=c_i$，否则代表 $S_i=S_{f_i}c_i$

接下来 $q$ 行，每行两个正整数 $i,j$，代表一组询问。

输出格式

$q$ 行，每行一个整数，代表一组询问的答案。

样例一

input

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

output

2
3
0
4

样例二

input

0 2 1
abca
jintianshikendejifengkuangxingqisivwowushi
1 2

output

35

样例解释

可惜这题没放到星期四考

样例三

input

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

4
1
1
1

数据范围与限制

时间限制 1.5s，空间限制 1GB

$T\in\{0,1\},1\leq n,q\leq 5\times 10^5$，$S_i$ 非空且只包含小写英文字符，$1\leq i,j\leq n$

当 $T=0$ 时，令 $L=\sum_{i=1}^n \left|S_i\right|$，保证 $L\leq 5\times 10^5$

当 $T=1$ 时，保证 $0\leq f_i\leq i-1$

子任务1（5分） $T=0,L\leq 1000$

子任务2（15分） $T=0$，所有 $\left|S_i\right|$ 全部相同。

子任务3（20分） $T=0,q=1$

子任务4（20分） $T=0$

子任务5（40分） 无特殊限制