Background

Problem Description

For strings $x, y$, define $w(x, y)$ as the number of occurrences of $x$ in $y$.

Index gives you $n$ strings $s_{1\dots n}$ and $m$ queries. Each query provides $l, r, k$. You need to compute $\max_{i=l}^r w(s_i, s_k)$.

Input Format

The first line contains two integers $n, m$.
The next $n$ lines each contain a string consisting only of lowercase letters, representing $s_{1\dots n}$.
The next $m$ lines each contain three integers $l, r, k$, representing a query.

Output Format

For each query, output one integer per line representing the answer.

6 3
dedicatus
a
misaka
mikoto
mi
aaa
1 5 6
1 2 4
1 5 4

3
0
1

Hint

Constraints

This problem uses bundled testdata.

For $100\%$ of the data, $1\le n, m\le 10^5$, $1\le \sum |s|\le 5\times 10^5$, $1\le l\le r\le n$, $1\le k\le n$.

Data: abruce&critnos&fjy666

Translated by ChatGPT 5