P8571 [JRKSJ R6] Dedicatus545


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)$.

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.

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

### Constraints This problem uses bundled testdata. | $\text{Subtask}$ | $n, q\le$ | $\sum\vert s\vert\le$ | $\text{Score}$ | Special property | | :----------: | :----------: | :----------: | :----------: |:----------: | | $1$ | $2\times10^3$ | $10^4$ | $20$ | None | | $2$ | $5\times10^4$ | $3\times 10^5$ | $20$ | None | | $3$ | $10^5$ | $5\times10^5$ | $20$ | All strings are pairwise distinct | | $4$ | $10^5$ | $5\times10^5$ | $40$ | None | 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