回文(version 3)
题号：NC316914
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

\hspace{15pt}给定一个长度为 n 且仅包含小写字母的字符串 s_1s_2\cdots s_n，给定 q 次询问的三元组 (l,r,x)，每次询问求区间 [l,r] 内有多少个长度为 x 的回文子序列。

【名词解释】
\hspace{15pt}回文串：若一个字符串从左向右读与从右向左读完全相同，则称其为回文串。
\hspace{15pt}子序列：从原字符串中删除任意个（可以为零、可以为全部）字符得到的新字符串。

输入描述:

\hspace{15pt}第一行两个整数 n,q(1\leqq n ,q\leqq 2\times 10^5)，表示字符串的长度和询问次数。

\hspace{15pt}第二行一个长度为 n 且仅包含小写字母的字符串 s。

\hspace{15pt}接下来 q 行 ，每行三个整数 l,r,x(1\leqq l\leqq r\leqq n,1\leqq x\leqq 3)，表示询问区间和询问回文子序列的长度。

输出描述:

\hspace{15pt}对于每次询问新起一行输出一个整数，表示当前询问区间有多少个长度为 x 的回文子序列。
示例1

输入

复制 
6 3
abcabc
1 3 1
1 4 2
1 6 3

输出

复制 
3
1
6