You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小智马上就要 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$。

提示

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