Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

G. Genes
time limit per test
5.5 s
memory limit per test
1024 megabytes
input
standard input
output
standard output

A DNA sequence is represented by a string $$$T$$$. Several genes are also known, represented by strings and ordered from most relevant to least relevant. The genes are numbered sequentially, starting from 1.

$$$Q$$$ queries are made. Each one delimits a segment of $$$T$$$, between indices $$$L_i$$$ and $$$R_i$$$, inclusive. For each query, the goal is to determine the index of the most relevant gene that occurs entirely as a substring of that segment.

Input

The first line of input contains the string $$$T$$$ ($$$1 \leq |T| \leq 10^{5}$$$). The second line contains the number $$$G$$$ of genes ($$$1 \leq G \leq 5 \times 10^{5}$$$). Each of the following $$$G$$$ lines contains a gene, from most to least relevant, one per line. Each gene is a non-empty string. It is guaranteed that the genes are distinct and that the sum $$$S$$$ of their lengths is at most $$$5 \times 10^{5}$$$.

The next line contains the number of queries $$$Q$$$ ($$$1 \leq Q \leq 10^{5}$$$). Each of the following $$$Q$$$ lines contains two integers $$$L_i$$$ and $$$R_i$$$ ($$$1 \leq L_i \leq R_i \leq |T|$$$), representing the inclusive bounds of the query.

All strings contain only the letters A, C, G, and T.

Output

For each query, print the index of the most relevant gene that occurs entirely within the corresponding segment of the DNA. If no gene occurs in that segment, print $$$-1$$$.

Examples
Input
ACAGACA
3
ACA
G
CA
3
1 7
2 6
1 2
Output
1
2
-1
Input
ACGT
2
ACGT
GT
2
1 3
2 4
Output
-1
2
Note

Explanation for example 1

In the first query, the segment is the entire sequence ACAGACA. The most relevant gene that occurs in it is ACA (index $$$1$$$).

In the second query, the segment is CAGAC. The most relevant gene that occurs in it is G (index $$$2$$$).

In the third query, the segment is AC. No gene occurs in this segment, so the answer is $$$-1$$$.