O talentoso 小 A foi escolhido como autor de problemas da ION2018 e agora precisa resolver a questão de dar um nome ao seu problema.
小 A foi escolhido como autor de problemas da ION2018. Preparou cuidadosamente um problema de qualidade muito elevada e já concluiu todo o trabalho, exceto a escolha do nome.
Como a ION já teve muitas edições, também existem regras para os nomes dos problemas. O manual de elaboração de problemas da ION estabelece que, a cada ano, a comissão escolhe uma cadeia de letras minúsculas, chamada cadeia de nomes desse ano. O nome de cada problema deve ser uma subcadeia contígua não vazia da cadeia de nomes desse ano e não pode ser igual ao nome de nenhum problema do ano anterior.
Por algumas razões especiais, 小 A não conhece os nomes dos problemas da ION2017, mas obteve a cadeia de nomes da ION2017 por certos meios especiais. Agora tem $Q$ consultas: em cada consulta, dadas as cadeias de nomes da ION2017 e da ION2018, determine quantos nomes de problema certamente satisfazem as regras da comissão, isto é, são subcadeias contíguas não vazias da cadeia de nomes da ION2018 e certamente não coincidem com o nome de nenhum problema da ION2017.
Por algumas razões especiais, as cadeias de nomes da ION2017 fornecidas em todas as consultas são subcadeias contíguas de uma mesma cadeia. Consulte os detalhes no formato de entrada.
Entrada
A primeira linha contém uma cadeia $S$. As cadeias de nomes da ION2017 fornecidas nas consultas seguintes são subcadeias contíguas de $S$.
A segunda linha contém um inteiro positivo $Q$, o número de consultas.
Cada uma das $Q$ linhas seguintes contém uma cadeia $T$ e dois inteiros positivos $l,r$. A consulta pergunta quantos nomes certamente satisfazem as regras se a cadeia de nomes da ION2017 for $S[l..r]$ e a cadeia de nomes da ION2018 for $T$.
É garantido que todas as cadeias fornecidas na entrada são constituídas por letras minúsculas.
Saída
Imprima $Q$ linhas. A linha $i$ deve conter um inteiro não negativo que representa a resposta à consulta $i$.
Exemplos
Entrada 1
scbamgepe 3 smape 2 7 sbape 3 8 sgepe 1 9
Saída 1
12 10 4
Exemplo 2
Consulte name/name2.in e name/name2.ans no diretório do participante.
Subtarefas
| Caso de teste | $\lvert S\rvert\le$ | $Q\le$ | $\sum\lvert T\rvert\le$ | Restrições das consultas | Outras restrições |
|---|---|---|---|---|---|
| 1 | $200$ | $200$ | $40000$ | $l=1,r=\lvert S\rvert$ em todas as consultas | $\lvert T\rvert\le200$ |
| 2 | $1000$ | $200$ | $40000$ | $l=1,r=\lvert S\rvert$ em todas as consultas | $\lvert T\rvert\le200$ |
| 3 | $1000$ | $200$ | $40000$ | $l=1,r=\lvert S\rvert$ em todas as consultas | $\lvert T\rvert\le200$ |
| 4 | $1000$ | $200$ | $5\cdot10^5$ | $l=1,r=\lvert S\rvert$ em todas as consultas | Nenhuma |
| 5 | $1000$ | $200$ | $5\cdot10^5$ | $l=1,r=\lvert S\rvert$ em todas as consultas | Nenhuma |
| 6 | $5\cdot10^5$ | $1$ | $5\cdot10^5$ | $l=1,r=\lvert S\rvert$ em todas as consultas | Nenhuma |
| 7 | $5\cdot10^5$ | $1$ | $5\cdot10^5$ | $l=1,r=\lvert S\rvert$ em todas as consultas | Nenhuma |
| 8 | $10^5$ | $10^5$ | $2\cdot10^5$ | $l=1,r=\lvert S\rvert$ em todas as consultas | Nenhuma |
| 9 | $10^5$ | $10^5$ | $2\cdot10^5$ | $l=1,r=\lvert S\rvert$ em todas as consultas | Cadeias aleatórias |
| 10 | $2\cdot10^5$ | $10^5$ | $4\cdot10^5$ | $l=1,r=\lvert S\rvert$ em todas as consultas | Nenhuma |
| 11 | $2\cdot10^5$ | $10^5$ | $4\cdot10^5$ | $l=1,r=\lvert S\rvert$ em todas as consultas | Cadeias aleatórias |
| 12 | $3\cdot10^5$ | $10^5$ | $6\cdot10^5$ | $l=1,r=\lvert S\rvert$ em todas as consultas | Nenhuma |
| 13 | $3\cdot10^5$ | $10^5$ | $6\cdot10^5$ | $l=1,r=\lvert S\rvert$ em todas as consultas | Cadeias aleatórias |
| 14 | $4\cdot10^5$ | $10^5$ | $8\cdot10^5$ | $l=1,r=\lvert S\rvert$ em todas as consultas | Nenhuma |
| 15 | $4\cdot10^5$ | $10^5$ | $8\cdot10^5$ | $l=1,r=\lvert S\rvert$ em todas as consultas | Cadeias aleatórias |
| 16 | $5\cdot10^5$ | $10^5$ | $8\cdot10^5$ | $l=1,r=\lvert S\rvert$ em todas as consultas | Nenhuma |
| 17 | $5\cdot10^5$ | $10^5$ | $8\cdot10^5$ | $l=1,r=\lvert S\rvert$ em todas as consultas | Cadeias aleatórias |
| 18 | $2\cdot10^5$ | $10^5$ | $10^6$ | Nenhuma | Nenhuma |
| 19 | $3\cdot10^5$ | $10^5$ | $10^6$ | Nenhuma | Nenhuma |
| 20 | $4\cdot10^5$ | $10^5$ | $10^6$ | Nenhuma | Nenhuma |
| 21 | $5\cdot10^5$ | $10^5$ | $10^6$ | Nenhuma | Nenhuma |
| 22 | $5\cdot10^5$ | $10^5$ | $10^6$ | Nenhuma | Nenhuma |
| 23 | $5\cdot10^5$ | $10^5$ | $10^6$ | Nenhuma | Nenhuma |
| 24 | $5\cdot10^5$ | $10^5$ | $10^6$ | Nenhuma | Nenhuma |
| 25 | $5\cdot10^5$ | $10^5$ | $10^6$ | Nenhuma | Nenhuma |
Para todos os dados, é garantido que $1\le l\le r\le\lvert S\rvert$ e $1\le\lvert T\rvert\le5\cdot10^5$.