[传智杯 #4 决赛] DDOSvoid 的馈赠
题目描述
小智马上就要 AK(All killed,指使本场比赛的全部题目 AC)本场“传智杯”全国大学生 IT 技能大赛(决赛)然后离场了。临走前,DDOSvoid 打算给小智 $n$ 个字符串 $s_1, s_2, \dots, s_n$ 作为纪念。在本题中,我们将这 $n$ 个字符串称作「模板串」。
小智本身有 $m$ 个字符串 $t_1, t_2, \dots t_m$。在本题中,我们将这 $m$ 个字符串称为「查询串」。
DDOSvoid 的礼物不是无条件的,他有 $q$ 个问题,每个问题给定两个参数 $x, y$,要求小智回答他:一共有多少个模板串 $s_i$,满足 $s_i$ 既是 $t_x$ 的子串,也是 $t_y$ 的子串?
只有回答对这 $q$ 个问题,小智才能得到 DDOSvoid 馈赠的礼物。请你帮帮小智,回他 DDOSvoid 的问题。
我们称一个字符串 $t$ 是 $s$ 的子串,当且仅当将 $s$ 的开头若干个(可以为 0 个)连续字符和结尾若干个(可以为 0 个)连续字符删去后,剩下的字符串和 $t$ 相同。例如,我们称 `ab` 是 `abc` 的子串,但 `ac` 不是 `abc` 的子串。
输入输出格式
输入格式
第一行有三个整数,依次表示模板串个数 $n$,查询串个数 $m$,以及询问的个数 $q$。
接下来 $n$ 行,每行一个字符串,依次表示模板串 $s_1,s_2, \dots s_n$。
接下来 $m$ 行,每行一个字符串,依次表示查询串 $t_1, t_2, \dots t_m$。
接下来 $q$ 行,每行两个整数 $x, y$,表示一个询问。
输出格式
对于每次询问,输出一行一个整数表示答案。
输入输出样例
输入样例 #1
3 2 1
a
b
c
ab
bac
1 2
输出样例 #1
2
输入样例 #2
3 3 3
aaba
baba
aba
ababa
aabab
babaa
1 2
1 3
2 3
输出样例 #2
1
2
1
说明
### 数据规模与约定
对于全部测试点,保证 $1\leq n,m,q,|s_i|,|t_i| \leq 10^5$,且模板串的长度之和、查询串的长度之和均不超过 $10^5$,即 $\sum\limits_{i = 1}^n |s_i|,\sum\limits_{i = 1}^m|t_i| \leq 10^5$,其中 $|x|$ 表示字符串 $x$ 的长度。保证输入的字符串只含有小写字母,$1 \leq x\neq y \leq m$。
### 提示
**请注意常数因子对程序效率造成的影响**。