题目背景

题目描述

对于字符串 $x,y$，定义 $w(x,y)$ 为 $x$ 在 $y$ 中的出现次数。

Index 给了你 $n$ 个字符串 $s_{1\dots n}$，$m$ 次询问，每次询问给定 $l,r,k$，求 $\max_{i=l}^r w(s_i,s_k)$。

输入格式

第一行两个整数 $n,m$。
下面 $n$ 行，每行一个只包含小写字母的字符串表示 $s_{1\dots n}$
下面 $m$ 行，每行三个整数 $l,r,k$ 表示询问。

输出格式

对于每个询问，每行输出一个整数表示答案。

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

3
0
1

提示

数据规模

本题采用捆绑测试。

对于 $100\%$ 的数据，$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