U186697 Zeta 的第八字符串

我买了八条跳绳，一条都不见了！ 我都讲了八分钟了，我真的不希望这种问题再出现了，我们都已经坐到四班了是吧……

$\zeta$ 还有大量的路要走，大量的桥要过。 渐渐地，他对人，对人，啊，对人性都感觉有点…… 于是他给出一个字符串，并且给出了集合 $\mathrm{ZT}$ 的定义： 对每个长度为 $n$ 的字符串 $s$ ，若 $s[1\dots i]=s[n-i+1\dots n]$ ，则 $s[1\dots i]\in \mathrm{ZT}$ 现在，$\zeta$ 将查询 $s[l\dots r]$ 组成的字符串的 $\mathrm{ZT}$ 集合中，长度大于 $k$ 的字符串有多少个。

第一行一个数 $n$ ，代表 $\zeta$ 给出的字符串长度。 接下来一行 $n$ 个小写字母组成的字符串 $s$ 。 下一行一个数 $m$ ，代表询问次数。 接下来 $m$ 行，每行三个数 $l,r,k$，意义如上。

对于每个询问，输出 $s[l\dots r]$ 组成的字符串的 $\mathrm{ZT}$ 集合中，长度大于 $k$ 的字符串数量。

对于 $100\%$ 的数据，$n,m\leq 5\times 10^4$