题目描述

Vadim 决定开拓新的领域，开始用斯塔罗巴尔语写说唱。

斯塔罗巴尔语共有 $N$ 个单词，字母表只包含 $26$ 个小写拉丁字母。这个语言中的每一个字母都会被读出，因此判断两个单词是否押韵相对直接。

对于两个长度至少为 $L$ 的单词，Vadim 可以分别选择它们长度相同、长度为 $L$ 的后缀。设这两个后缀在对应位置上共有 $d$ 个字符不同，则这对后缀的押韵值为

Vadim 可以自行选择后缀长度，因此两个单词的押韵值等于所有等长后缀对的押韵值中的最大值。

现在有 $Q$ 个询问。每个询问给出两个单词，并规定先从这两个单词的末尾各删除相同数量的字符。请计算删除后两个单词的押韵值。

输入格式

第一行包含两个整数 $N,Q$，分别表示单词数量和询问数量。

接下来 $N$ 行，第 $i$ 行包含一个仅由小写拉丁字母组成的字符串 $s_i$。

接下来 $Q$ 行，每行包含三个整数 $u_i,v_i,c_i$：

• $u_i,v_i$ 表示本次询问选择的两个单词编号；
• $c_i$ 表示从两个单词末尾分别删除的字符数。

满足

保证所有单词的总长度不超过 $10^6$：

输出格式

输出 $Q$ 行，第 $i$ 行输出第 $i$ 个询问的押韵值。

若你的答案为 $x$，标准答案为 $y$，当满足

时，答案会被接受。

样例

5 7
fate
cmake
stake
cfake
cmate
1 2 0
2 3 0
1 4 0
2 5 0
1 5 0
1 4 1
2 5 2

1.5
3
2
2.5
3
1.5
3