Problem F
Rap Queries

Fernando is an accomplished rapper. He is very fast, not only when singing, but also to compose his raps. But behind his success in composition, there is a method based on data analysis.

Fernando has a sequence of $n$ words that he knows fit raps well. He receives several requests (queries) to make raps every day. Each query is defined by the integers $l$, $r$ and $t$, parameters defined from the target audience of the rap he is asked to make.

For each query Fernando must choose the maximum number of words that $t$-rhyme in the range from $l$ to $r$ inclusive from his list. A set of words $t$-rhyme if every word in the set has the same suffix of length $t$. A suffix of length $t$ is the last $t$ letters of a word. Words with a size less than $t$ never $t$-rhyme and can never be chosen in a query with parameter $t$. And also equal words in different positions are considered different.

Help Fernando answer for each query the maximum number of words he can choose respecting the restrictions and maybe he’ll give you a ticket for his next show!

Input

The first line of the input contains one integer $n$ the number of words in Fernando’s list ($1 \leq n \leq 10^5$), followed by $n$ lines, each with a word consisting only of lower case letters of the Latin alphabet. The sum of the sizes of all words does not exceed $2\cdot 10^5$. The next line contains the integer $q$ the number of queries ($1 \leq q \leq 2\cdot 10^5$) followed by $q$ lines, each with the integers $l$, $r$ and $t$ ($1 \leq l \leq r \leq n, 1 \leq t \leq 2\cdot 10^5$) the parameters of each query. Words are numbered from $1$ to $n$ in the order they are read in the input.

Output

Print $q$ lines, each with an integer, the maximum number of words Fernando can choose for each query.

10
tudo
vale
a
pena
se
a
alma
nao
e
pequena
5
1 10 1
4 10 3
4 10 4
2 4 100
1 1 4

5
2
1
0
1