重排的回文串
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld

题目描述

给一个长为 n 的只含小写字母的字符串

每次查询一个区间 [l,r] 内，有多少子区间可以重排为一个回文串

一个区间可以重排为一个回文串：

就是说我们可以以一定顺序排列这个区间内的所有数使得排列后为一个回文串


输入描述:

第一行两个正整数n,m
第二行一个长为 n 的字符串
之后 m 行每行两个数 l 和 r

输出描述:

对于每个询问，输出一个整数表示答案
示例1

输入

复制 
6 5
zzqzzq
2 4
3 4
2 3
4 5
1 1

输出

复制 
4
2
2
3
1

说明

[2,4]为zqz,其中[2,2],[3,3],[4,4],[2,4]都可以重排为一个回文串
[3,4]为qz,其中[3,3],[4,4]可以重排为一个回文串
[2,3]为zq,其中[2,2],[3,3]可以重排为一个回文串
[4,5]为zz,其中[4,4],[5,5],[4,5]可以重排为一个回文串
[1,1]为z,只有这一个区间且其可以重排为一个回文串

备注:

对于100%的数据，有n , m <= 60000