小 Δ 的字符串水平终于达到了普及组水平！他学会了求一个字符串在另一个字符串中的出现次数，但他意识到了这是为人熟知的原题，不能出到互测里。过了几天，小 Δ 开始学习提高组字符串算法，比如求一个字符串的最长回文子串，但这也是为人熟知的原题。但小 Δ 觉得只需要融合一下这两道题，就不算为人熟知的原题了，他出的题目如下。
对于一个字符串 S=a1a2a3⋯ak，定义字符串的长度 |S|=k，定义 S 的子串 [l,r] 为 S[l,r]=alal+1⋯ar，并定义其反转为 SR=akak−1⋯a1
定义一个字符串 S 的回文集合是其中所有回文串的位置的集合，也就是 P(S)={(l,r)∈Z2∣1≤l≤r≤|S|,S[l,r]=(S[l,r])R}
定义两个字符串 S,T 回文匹配，记为 S≈T， 当且仅当 P(S)=P(T)
给定 n 个字符串 Si，令 f(i,j) 为 Sj 有多少个子串与 Si 回文匹配，也就是 f(i,j)=|{(l,r)∈Z2∣1≤l≤r≤|Sj|,Sj[l,r]≈Si}|
给定 q 次询问，每次给定 i,j，求 f(i,j)
本题有两种输入方式，第一种是直接给出 Si，第二种是把 Si 给定为其前面的某一个 Sfi 后面接上一个字符 ci，见输入格式。
输入格式
第一行，三个整数 T,n,q
若 T=0，则接下来 n 行，第 i 行一个字符串 Si
若 T=1，则接下来 n 行，第 i 行一个整数 fi，和一个字符 ci，若 fi=0，则代表 Si=ci，否则代表 Si=Sfici
接下来 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∈{0,1},1≤n,q≤5×105，Si 非空且只包含小写英文字符，1≤i,j≤n
当 T=0 时，令 L=∑ni=1|Si|，保证 L≤5×105
当 T=1 时，保证 0≤fi≤i−1
子任务1（5分） T=0,L≤1000
子任务2（15分） T=0，所有 |Si| 全部相同。
子任务3（20分） T=0,q=1
子任务4（20分） T=0
子任务5（40分） 无特殊限制