Problem F
Rap Queries

Fernando é um exímio rapper. Ele é muito veloz, não só ao cantar, mas também para compor seus raps. Mas por de trás de seu sucesso na composição, há um método baseado em análise de dados.

Fernando têm uma sequência de $n$ palavras que ele sabe que caem bem em raps. Ele recebe várias requisições (queries) para fazer raps todos os dias. Cada query é definida pelos inteiros $l$, $r$ e $t$, parâmetros definidos a partir do público alvo para o qual o rap deve ser feito.

Para cada query Fernando deve escolher, das palavras no intervalo de $l$ a $r$ incluso de sua lista, o número máximo de palavras que $t$-rimam entre si. Palavras $t$-rimam entre si se todas têm um sufixo de tamanho $t$ em comum. Um sufixo de tamanho $t$ são as $t$ últimas letras de uma palavra. Palavras com tamanho menor que $t$ nunca $t$-rimam e nunca podem ser escolhidas em um query com parâmetro $t$. E palavras iguais em posições diferentes são consideradas diferentes.

Ajude Fernando a responder, para cada query, o número máximo de palavras que ele consegue escolher respeitando as restrições e talvez ele te de um ingresso para seu próximo show!

Input

A primeira linha do input contém um inteiro $n$ o número de palavras na lista de Fernando ($1 \leq n \leq 10^5$), seguidos de $n$ linhas, cada uma com uma palavra consistindo apenas de letras minúsculas do alfabeto latino. A soma dos tamanhos de todas as palavras não excede $2\cdot 10^5$. Em seguida lê-se o inteiro $q$ o número de querys ($1 \leq q \leq 2\cdot 10^5$) seguido de $q$ linhas, cada uma com os inteiros $l$, $r$ e $t$ ($1 \leq l \leq r \leq n , 1 \leq t \leq 2\cdot 10^5$) os parâmetros de cada query. As palavras são númeradas de $1$ a $n$ na ordem em que são lidas no input.

Output

Imprima $q$ linhas, cada uma com um inteiro, o número máximo de palavras que Fernando pode escolher em cada 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