TLE '16 Contest 7 P6 - Everyone Hates Reading - Olympiads Online Judge

TLE '16 Contest 7 P6 - Everyone Hates Reading

Points: 15

Time limit: 0.6s

Memory limit: 256M

Author:

imaxblue

Problem types

Your brain after reading certain books.

Your neighbourhood fox has another English project. There's only one problem … it involves reading. ~~Foxen~~ Everyone hates reading and will do anything to avoid it.

Your neighbourhood fox is given a long article of text, containing $N$ $N$ words. He is then given $M$ $M$ root words which he must research, and a range $[l, r]$ $[l, r]$ in the text to use. Of the words from $l$ $l$ to $r$ $r$ , please help him count the number of words that either has the root word as a prefix or is a prefix of the root word.

Constraints

$N \le 100\,000$ $N \leq 100 000$

$M \le 100\,000$ $M \leq 100 000$

The total length of all words in the article of text and the root words will each be no greater than $100\,000$ $100 000$ .

Input Specification

2 integers, $N$ $N$ and $M$ $M$ .

$N$ $N$ lines, each with a string of lowercase English letters.

$M$ $M$ lines, each with a string of lowercase English letters and 2 integers $l$ $l$ and $r$ $r$ .

Output Specification

$N$ $N$ lines, each with an integer: the answer to each of the queries.

Sample Input

Copy

3 3
a
ab
abc
a 1 3
abcerhfgdryrtjfhdgshdj 2 3
aaaaaaaaa 1 3

Sample Output

Copy

3
2
1

Comments

2

zxyl commented on May 15, 2018, 4:01 p.m.

Are all root words guaranteed to be distinct?