U405333 帕鲁大陆迷路的一天

**[P3604 美好的每一天](https://www.luogu.com.cn/problem/P3604) 强化版** 帕鲁世界太大了，今天小帕鲁出去游玩，发现到处都是迷雾，好不容易快要到家了，发现家门口处的一条小路生成了迷雾。当前位置为 $1$，家门口所在位置为 $n$。而迷雾又有不同的种类，每个种类用一个 **小写英文字母** 表示。小帕鲁发现，对于某一段范围的迷雾，它可以把它们自由地交换位置，如果能够使这段区间的迷雾对称，那么就能够驱散这部分的迷雾。这并不是一件难事，但聪明的小帕鲁想到了一个问题，对于一个区间内的连续子区间里有多少个子区间的迷雾可以被这样的操作消散。帕鲁想不出这个问题的答案，请聪明的你来帮忙解决。

给定一个 $n$ 表示家所在的位置，小路范围即为 $1\sim n$。并且给出一个长为 $n$ 的字符串，表示 $[1,n]$ 每个位置的迷雾种类。接下来给出 $q$ 个查询，每个查询你需要回到 $[l,r]$ 中有多少个**连续子区间**满足重排以后是 **回文串**。

第一行输入两个数 $n$ 和 $q$。 第二行输入一个长为 $n$ 的字符串，由**小写英文字母组成**。 接下来 $q$ 行每行输入 $l$ 和 $r$。 所有的 $n,q \le 5 \times 10^5$。

对于每一个询问输出一行表示答案。

$subtask$ 情况： 0. $n,q \le 1e3$，$5\ 分$。 1. $n,q \le 1e4$，$10\ 分$。 2. $n,q \le 1e5$，$15\ 分$。 3. $n,q \le 3e5$，$30\ 分$。 4. $n,q \le 5e5$，$40\ 分$。 最后一个时限 $3s$，其余时限 $2.5s$，空间 $512 mb$。