Maximum Occurrence Query

Given two strings \(x\) and \(y\), define \(w(x,y)\) as the number of occurrences of \(x\) in \(y\) (allowing overlapping occurrences).

You are given \(n\) strings \(s_1, s_2, ..., s_n\) and \(m\) queries. Each query is represented by three integers \(l, r, k\). For each query, you should compute:

\[ \max_{i=l}^{r} w(s_i, s_k) \]

Here, \(s_k\) is one of the given strings and you need to find the maximum occurrence count of \(s_i\) in \(s_k)\) for \(i\) between \(l\) and \(r\) (inclusive).

Print one integer per query representing the answer.

inputFormat

The first line contains two integers \(n\) and \(m\), representing the number of strings and the number of queries respectively.

The following \(n\) lines each contain a non-empty string \(s_i\).

The next \(m\) lines each contain three integers \(l\), \(r\), and \(k\), describing a query.

outputFormat

For each query, output a single integer on a new line which is the maximum value of \(w(s_i, s_k)\) for \(l \le i \le r\).

sample

3 2
ab
aba
abab
1 2 2
1 3 3

1
2