NOI '18 Problem 3 - Name - DMOJ: Modern Online Judge

NOI '18 Problem 3 - Name

Points: 25 (partial)

Time limit: 4.0s

Memory limit: 1G

Problem types

You are given a string $S$ ~S~, and $q$ ~q~ queries.

For each query, you are given a string $T$ ~T~ and two integers $l$ ~l~, $r$ ~r~. You are asked to output the number of distinct substrings of $T$ ~T~ that is not a substring of $S[l..r]$ ~S[l..r]~

String $S[l..r]$ ~S[l..r]~ refers the substring of $S$ ~S~ from index $l$ ~l~ to $r$ ~r~, i.e. $s_l s_{l+1} ... s_{r-1} s_r$ ~s_l s_{l+1} ... s_{r-1} s_r~.

Input Specification

The first line contains an string $S$ ~S~.

The next line contains an integer $q$ ~q~.

Each of the next $q$ ~q~ lines contains a string $T$ ~T~ and two integers $l$ ~l~, $r$ ~r~.

Output Specification

For each test case, output the answer.

Sample Input

scbamgepe
3
smape 2 7
sbape 3 8
sgepe 1 9

Sample Output

12
10
4

Data ranges

Case	$\mid S \mid \leq$ ~\mid S \mid \leq ~	$Q \leq$ ~ Q \leq ~	$\sum \mid T\mid \leq$ ~\sum \mid T\mid \leq~	Properties
$1$ ~1~	$200$ ~200~	$200$ ~200~	$40000$ ~40000~	$T\leq 200$ ~T\leq 200~
$2$ ~2~	$1000$ ~1000~	$200$ ~200~	$40000$ ~40000~	$T\leq 200$ ~T\leq 200~
$3$ ~3~	$1000$ ~1000~	$200$ ~200~	$40000$ ~40000~	$T\leq 200$ ~T\leq 200~
$4$ ~4~	$1000$ ~1000~	$200$ ~200~	$5 \times 10^5$ ~5 \times 10^5~	None
$5$ ~5~	$1000$ ~1000~	$200$ ~200~	$5 \times 10^5$ ~5 \times 10^5~	None
$6$ ~6~	$5 \times 10^5$ ~5 \times 10^5~	$1$ ~1~	$5 \times 10^5$ ~5 \times 10^5~	None
$7$ ~7~	$5 \times 10^5$ ~5 \times 10^5~	$1$ ~1~	$5 \times 10^5$ ~5 \times 10^5~	None
$8$ ~8~	$10^5$ ~10^5~	$10^5$ ~10^5~	$2 \times 10^5$ ~2 \times 10^5~	None
$9$ ~9~	$10^5$ ~10^5~	$10^5$ ~10^5~	$2 \times 10^5$ ~2 \times 10^5~	string is random
$10$ ~10~	$2 \times 10^5$ ~2 \times 10^5~	$10^5$ ~10^5~	$4 \times 10^5$ ~4 \times 10^5~	None
$11$ ~11~	$2 \times 10^5$ ~2 \times 10^5~	$10^5$ ~10^5~	$4 \times 10^5$ ~4 \times 10^5~	String is Random
$12$ ~12~	$3 \times 10^5$ ~3 \times 10^5~	$10^5$ ~10^5~	$6 \times 10^5$ ~6 \times 10^5~	None
$13$ ~13~	$3 \times 10^5$ ~3 \times 10^5~	$10^5$ ~10^5~	$6 \times 10^5$ ~6 \times 10^5~	string is random
$14$ ~14~	$4 \times 10^5$ ~4 \times 10^5~	$10^5$ ~10^5~	$8 \times 10^5$ ~8 \times 10^5~	None
$15$ ~15~	$4 \times 10^5$ ~4 \times 10^5~	$10^5$ ~10^5~	$8 \times 10^5$ ~8 \times 10^5~	string is random
$16$ ~16~	$5 \times 10^5$ ~5 \times 10^5~	$10^5$ ~10^5~	$10^6$ ~10^6~	None
$17$ ~17~	$5 \times 10^5$ ~5 \times 10^5~	$10^5$ ~10^5~	$10^6$ ~10^6~	String is random
$18$ ~18~	$2 \times 10^5$ ~2 \times 10^5~	$10^5$ ~10^5~	$10^6$ ~10^6~	None
$19$ ~19~	$3 \times 10^5$ ~3 \times 10^5~	$10^5$ ~10^5~	$10^6$ ~10^6~	none
$20$ ~20~	$4 \times 10^5$ ~4 \times 10^5~	$10^5$ ~10^5~	$10^6$ ~10^6~	none
$21$ ~21~	$5 \times 10^5$ ~5 \times 10^5~	$10^5$ ~10^5~	$10^6$ ~10^6~	none
$22$ ~22~	$5 \times 10^5$ ~5 \times 10^5~	$10^5$ ~10^5~	$10^6$ ~10^6~	none
$23$ ~23~	$5 \times 10^5$ ~5 \times 10^5~	$10^5$ ~10^5~	$10^6$ ~10^6~	none
$24$ ~24~	$5 \times 10^5$ ~5 \times 10^5~	$10^5$ ~10^5~	$10^6$ ~10^6~	none
$25$ ~25~	$5 \times 10^5$ ~5 \times 10^5~	$10^5$ ~10^5~	$10^6$ ~10^6~	none