Problem Description

Xiao Zhi is about to AK (All killed, meaning getting AC on all problems in this contest) the "Chuanzhi Cup" National College Student IT Skills Competition (Finals) and then leave. Before he leaves, DDOSvoid plans to give Xiao Zhi $n$ strings $s_1, s_2, \dots, s_n$ as a souvenir. In this problem, we call these $n$ strings "template strings".

Xiao Zhi already has $m$ strings $t_1, t_2, \dots t_m$. In this problem, we call these $m$ strings "query strings".

DDOSvoid's gift is not unconditional. He has $q$ questions. Each question gives two parameters $x, y$ and asks Xiao Zhi: how many template strings $s_i$ satisfy that $s_i$ is both a substring of $t_x$ and a substring of $t_y$?

Only if Xiao Zhi answers these $q$ questions correctly can he receive DDOSvoid's gift. Please help Xiao Zhi answer DDOSvoid's questions.

We say a string $t$ is a substring of $s$ if and only if, after deleting some (possibly $0$) consecutive characters from the beginning of $s$ and some (possibly $0$) consecutive characters from the end of $s$, the remaining string is exactly $t$. For example, ab is a substring of abc, but ac is not a substring of abc.

Input Format

The first line contains three integers, in order: the number of template strings $n$, the number of query strings $m$, and the number of queries $q$.
The next $n$ lines each contain one string, representing the template strings $s_1, s_2, \dots s_n$ in order.
The next $m$ lines each contain one string, representing the query strings $t_1, t_2, \dots t_m$ in order.
The next $q$ lines each contain two integers $x, y$, representing a query.

Output Format

For each query, output one line with one integer, the answer.

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

Hint

Constraints

For all testdata, it is guaranteed that $1\leq n,m,q,|s_i|,|t_i| \leq 10^5$, and the total length of template strings and the total length of query strings are both at most $10^5$, i.e., $\sum\limits_{i = 1}^n |s_i|,\sum\limits_{i = 1}^m|t_i| \leq 10^5$, where $|x|$ denotes the length of string $x$. It is guaranteed that the input strings contain only lowercase letters, and $1 \leq x\neq y \leq m$.

Hint

Please pay attention to the impact of constant factors on program efficiency.

Translated by ChatGPT 5