The ancient book - MarisaOJ: Marisa Online Judge

Explorer Reisen, after entering a mysterious castle, found an ancient book. Reisen noticed that the book consists of

$n$ pages, with each page containing exactly one sentence. The sentence on the

$i$ -th page is represented by a string

$S_i$ , which consists only of lowercase Latin letters. Moreover, she cannot understand the meaning of the sentences but decides to try deciphering them. Reisen carries out

$q$ studies. The

$i$ -th study involves the numbers

$l_i, r_i, k_i$ , indicating that she will analyze the sentences on pages from

$l_i$ to

$r_i$ , using the sentence on page

$k_i$ as the reference to measure the degree of similarity among them. The similarity of this dataset is defined as the total length of the longest common prefixes (LCP) between each analyzed sentence and the reference sentence. For each study, help Reisen calculate the similarity of the dataset to decode the book. ### Input - The first line contains two positive integers

$n, q$ . - The next

$n$ lines, the

$i$ -th line, contain the string

$S_i$ . - The next

$q$ lines, the

$i$ -th line, contain three positive integers

$l_i, r_i, k_i$ . ### Output - Print

$q$ lines, each containing the result of a study. ### Constraints -

$1 \leq n, q \leq 5 \cdot 10^4$ . - The total length of all strings does not exceed

$5 \cdot 10^4$ . - For all queries,

$1 \leq l_i, r_i, k_i \leq n$ with

$1 \leq i \leq q$ . ### Example Input

$6 5 abbcde abge xyz abbcx xyuvt abbbbb 1 3 6 1 6 4 3 5 3 1 2 4 3 6 1$

Output

$5 14 5 6 7$

Introduction to Trie
	Prefix
	Compare string
	Maximum score
	Report
	Maximum XOR subarray
	Query on string
	Language
	Poem
	Palindrome pairs
	Mass XOR queries
	XOR-path on tree
	The ancient book

Topic

Tree

Data structure

Rating

2100

Source

MarisaOJ Original

Solution (0)

Solution