Migrated from Lutece 2416 第六章：最终决战

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

上一集：上一集

第六章：最终决战

奄奄一息的熊，依然死守着监狱的大门。

「我与你无冤无仇，让开吧。」糖怜悯的看着熊，熊当年也是赫赫有名的人物，可如今在自己面前却显得如此不值一提。

「咳，我不。。。」熊刚想说不，突然，他好像看到了什么，震惊地瞪大了双眼。

「詹皇，你怎么会。。。」

「不会真的有人觉得我能打得过熊吧，不会吧不会吧不会吧。」詹皇一瞬间闪现到熊的面前，用鲜红的码力包裹着自己的手，伸进了熊的金色码力里，然后，码力中传来破碎的声音。

「把你编译器给扬了。」 詹皇咧嘴大笑。

熊震惊地看着詹皇来的位置。马兔狗三人，貌似也已经被卸载了编译器。

「你什么时候！」熊绝望地大喊。

「不会真的有人觉得我能开门吧，不会吧不会吧不会吧。」詹皇用他的码力击碎了监狱最深的牢门。

「终于有人，来救我了吗？」 里面传来低沉的声音。同时，漆黑的码力瞬间布满整个监狱。这正是力量的味道。

「 Vingying 大人，您终于回来了」 詹 皇 狂 喜。

而 Vingying 边上出现了两个身影，正是 HeRaNO 和 ZXyang。

「我们奋力守护的东西，终究还是被打破了吗」 熊咬牙切齿地，一个字一个字吐出来。

「可真是要感谢你呢糖糖」 HeRaNO 笑着说。

「你们到底怎么回事，你们守护的究竟是什么！」糖大声诘问。

「呵呵呵，哈哈哈」 三个人不约而同地笑了起来。

「想知道我们守护的东西吗。。。」

「糖糖，我大括号换行啦」

大括号换不换行，自古以来便是一个纷争的问题。直到很久以前，不换行派在世界大战中取得了胜利。从此而来，代码风格被逐渐规范，换行派慢慢地推出了江湖，或者蛰伏于难以被发现的地方，悄悄拓展实力，随时准备复辟，或者干脆就暂时加入不换行派，每天在修炼过程中忍受身心的煎熬。直到有一天，天灾来临了，Vingying 被换行派选中，承担起了恢复换行派复兴的使命。

「在燃烧的远征开始的时候，我诱使 ZXyang 和 HeRaNO 也尝试了换行，现在，他们两个也是坚定的换行派了。」

「在修复完大地的损伤后，我一度想要籍此机会复辟王朝，但是却被那些老古董关了起来，并且用熊马兔狗四神兽封印了我的力量。」

「而所幸我的两个队友还在。即使没有人能成功救出我，他们也可以想其他办法。」

「他们发现，在遥远的东方有一个算法天才少女，也就是你，糖糖。」

ZXyang 听到这里点了点头：「我并不是被贬到远东的，而是我自愿下放的。而我的能力也并不是因为什么天地灵气差劲，而是因为我犯了天诛。整个代码大陆其实是一个巨大的数据库，我动用我所有码力，短暂地黑进了系统，并且篡改了狗的信息。原本狗也是守卫监狱的四神兽之一，但是我把他修改成了你的发小，并且修改了所有人的记忆中关于狗的记录。就这样，我们才可以让你一步一步，朝着我们计划的方向前进，让你们自相残杀。」

詹皇狂笑：「三年又三年，到如今已经十年了，我一直潜伏着自己。熊、狗、马、糖，你们这些写代码不换行的，都应该给我死。」

Vingying 邪魅一笑：「糖糖，念在你救我有功，现在还有机会加入我们换行派。」

糖浑身颤抖，粉红色的码力中透露着肉眼可见的愤怒：

「谁管你们换不换行啊！！！！！！」

「蛤蛤蛤，看来你是敬酒不吃吃罚酒了。让我来告诉你，什么叫真正的大巧不工。」

「听好了！ $n$ 个字符串 $s_1,s_2\dots s_n$ ，每次我都会询问三个参数 $l,r,k$，你必须要告诉我所有的 $s_l,s_{l+1}\dots s_r$ 在 $s_k$ 中出现了多少次！」

最后的决战开始了 （下一章会在数学与几何专题更新，大概）

Input

第一行给出两个数 $n$ ， $q$ 接下来 $n$ 行给出 $n$ 个字符串。 接下来 $q$ 行每行给出三个数 $l,r,k$

Output

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

Samples

7 5
qwq
orz
o
ohhhhhhhhhhh
qwqwqwqoqwqwqwq
zroqwqorz
hhh
2 6 5
1 6 6
3 4 4
1 7 4
2 4 3

2
5
2
11
1

Constraints

$n,q,\sum\limits_{i=1}^n |s_i| \leq 10^5$ $1\leq l,r,k\leq n,l\leq r$

Note

对于样例的第四组询问。 串 3 o 在串4 ohhhhhhhhhhh 中出现一次 串 4 ohhhhhhhhhhh 在串 4 ohhhhhhhhhhh 中出现一次 串 7 hhh 在串 4 ohhhhhhhhhhh 中出现9次 所以答案是11

Resources

2020 UESTC ICPC Training for String and Search Algorithm