Template Substring Query

In this problem, you are given n template strings \(s_1, s_2, \dots, s_n\) and m query strings \(t_1, t_2, \dots, t_m\). There are also q queries. Each query consists of two integers \(x\) and \(y\). For each query, you need to count how many template strings \(s_i\) are substrings of both \(t_x\) and \(t_y\).

A string \(t\) is said to be a substring of a string \(s\) if and only if \(t\) can be obtained by removing some (possibly zero) consecutive characters from the beginning of \(s\) and some (possibly zero) consecutive characters from the end of \(s\). For example, we regard ab as a substring of abc, but ac is not a substring of abc.

You must answer all queries correctly to receive the gift. Help our hero answer DDOSvoid's questions!

inputFormat

The first line contains three integers n, m and q indicating the number of template strings, the number of query strings, and the number of queries, respectively.

The next n lines each contain a non-empty string \(s_i\) (the template strings).

The following m lines each contain a non-empty string \(t_i\) (the query strings).

The next q lines each contain two integers \(x\) and \(y\) (1-indexed) representing a query.

outputFormat

For each query, output a single integer on a new line representing the number of template strings that are substrings of both \(t_x\) and \(t_y\).

sample

3 3 3
a
ab
bc
abc
bab
ac
1 2
1 3
2 3

2
1
1