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$ 的字符串有多少个。

无

无

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