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. After reading through the book, Reisen realized that all the sentences are distinct. 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
```
