Counting Memorized Word Occurrences in an Article

Given an English article consisting of N words and a list of M words that a student has memorized, your task is to answer Q queries. In each query, you are provided with a range [L, R] (1-indexed) corresponding to the article segment. For each query, output the total number of times the memorized words appear in that segment.

Use the following formula for each query answer:

where prefix[i] is the cumulative count of memorized word occurrences from the beginning of the article up to the i-th word.

inputFormat

The first line contains three integers: N, M, and Q, representing the number of words in the article, the number of memorized words, and the number of queries respectively.

The second line contains N space-separated words representing the article.

The following M lines each contain one memorized word.

The next Q lines each contain two integers L and R (1-indexed), representing a query interval in the article.

outputFormat

For each of the Q queries, output the total number of times the memorized words appear in the article segment from position L to R (inclusive). Each answer should be printed on a new line.

sample

9 3 2
the quick brown fox jumps over the lazy dog
the
fox
dog
1 9
3 5

4
1