题目描述

小智马上就要 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$，表示一个询问。

输出格式

对于每次询问，输出一行一个整数表示答案。

3 2 1
a
b
c
ab
bac
1 2

2

3 3 3
aaba
baba
aba
ababa
aabab
babaa
1 2
1 3
2 3

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$。

提示

请注意常数因子对程序效率造成的影响。