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~ words. He is then given ~M~ root words which he must research, and a range ~[l, r]~ in the text to use. Of the words from ~l~ to ~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.
~N \le 100\,000~
~M \le 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~.
~2~ integers, ~N~ and ~M~.
~N~ lines, each with a string of lowercase English letters.
~M~ lines, each with a string of lowercase English letters and 2 integers ~l~ and ~r~.
~N~ lines, each with an integer: the answer to each of the queries.
3 3 a ab abc a 1 3 abcerhfgdryrtjfhdgshdj 2 3 aaaaaaaaa 1 3
3 2 1