给定一个长度为 且仅包含小写字母的字符串 ，给定 次询问的三元组 ，每次询问求区间 内有多少个长度为 的回文子序列。 【名词解释】 回文串：若一个字符串从左向右读与从右向左读完全相同，则称其为回文串。 子序列：从原字符串中删除任意个（可以为零、可以为全部）字符得到的新字符串。

输入描述:

第一行两个整数 ，表示字符串的长度和询问次数。第二行一个长度为 且仅包含小写字母的字符串 。接下来 行 ，每行三个整数 ，表示询问区间和询问回文子序列的长度。

输出描述:

对于每次询问新起一行输出一个整数，表示当前询问区间有多少个长度为 的回文子序列。