Shakespeare is writing a soliloquy for his newest play. The soliloquy is represented as a string of $$$N$$$ characters. Shakespeare has a set of $$$M$$$ distinct words where the sum of the word lengths for all words in the set is no greater than $$$10^5$$$. Shakespeare has $$$Q$$$ intervals that cover some portion of the soliloquy. He wants to know, for each interval, how many substrings in that interval are words in the set.
The first line of input contains $$$N,\ M,\ Q\ (1 \leq N \leq 5\cdot 10^4, 1 \leq M, Q \leq 10^5)$$$.
The second line of input contains a string of size $$$N$$$ representing the soliloquy.
The next $$$M$$$ lines each contain a word in the set. The sum of all $$$M$$$ word lengths is no greater than $$$10^5$$$.
The next $$$Q$$$ lines each contain two numbers $$$l_i, r_i,\ (1 \leq l_i \leq r_i \leq N)$$$ representing the $$$i^{th}$$$ query interval.
Note: All characters in all strings contain only uppercase letters between $$$A$$$ and $$$Z$$$.
Please output $$$Q$$$ lines, where the $$$i^{th}$$$ line contains the answer to the $$$i^{th}$$$ query.
12 4 3ABCDABCDABCDABCDBCA4 75 121 1
3 8 1
5 5 1AAAAAAAAAAAAAAAAAAAA1 5
15
Let's break down the queries in the first sample case.
The first query is an interval on positions $$$[4, 7]$$$ of the soliloquy corresponding to the substring "DABC". In this interval, there is $$$1$$$ occurrence of word "AB", $$$1$$$ occurrence of "BC", and $$$1$$$ occurrence of "A", so the answer is $$$1+1+1=3$$$.
The second query is an interval on positions $$$[5, 12]$$$ of the soliloquy corresponding to the substring "ABCDABCD". In this interval, there are $$$2$$$ occurrences of word "AB", $$$2$$$ occurrences of "CD", $$$2$$$ occurrences of "BC", and $$$2$$$ occurrences of "A", so the answer is $$$2+2+2+2=8$$$.
The third query is an interval on position $$$[1, 1]$$$ of the soliloquy corresponding to the substring "A". In this interval, there is just $$$1$$$ occurrence of word "A", so the answer is $$$1$$$.
