[传智杯 #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` 的子串。 ## Input 第一行有三个整数，依次表示模板串个数 $n$，查询串个数 $m$，以及询问的个数 $q$。 接下来 $n$ 行，每行一个字符串，依次表示模板串 $s_1,s_2, \dots s_n$。 接下来 $m$ 行，每行一个字符串，依次表示查询串 $t_1, t_2, \dots t_m$。 接下来 $q$ 行，每行两个整数 $x, y$，表示一个询问。 ## Output 对于每次询问，输出一行一个整数表示答案。 [samples] ## Note ### 数据规模与约定 对于全部测试点，保证 $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$。 ### 提示 **请注意常数因子对程序效率造成的影响**。