#1272. [Ynoi2017]由乃的商场之旅

[Ynoi2017]由乃的商场之旅

Description

由乃有一天去参加一个商场举办的游戏。商场派了一些球王排成一行。每个人面前有几堆球。说来也巧,由乃和你

一样,觉得这游戏很无聊,于是决定换一个商场。另一个商场是Deus的,他看到由乃来了,于是想出了一个更有趣

的游戏:写数据结构题这个题是这样的:

我们的情人,不过是随便借个名字,用幻想吹出来的肥皂泡,把信拿去吧,你可以使假戏成真。我本来是无病呻吟

,漫无目的的吐露爱情---现在这些漂泊不定的鸟儿有地方栖息了,你可以从信里看出来。拿去吧---由于不是出自

真心,话就说得格外动听,拿去吧,就这么办吧...由于世界会在7月20日完结,作为救世主,间宫卓司要在19日让

所有人回归天空现在已经是19日傍晚,大家集合在C栋的天台上,一共n个人在他们面前,便是终之空,那终结的天

回归天空是一件庄重的事情,所以卓司决定让大家分批次进行,给每个人给了一个小写字母'a'->'z'作为编号一个

区间的人如果满足他们的编号重排之后可以成为一个回文串,则他们可以一起回归天空,即这个区间可以回归天空

由于卓司是一个喜欢妄想的人,他妄想了m个区间,每次他想知道每个区间中有多少个子区间可以回归天空因为世

界末日要来了,所以卓司的信徒很多

由乃天天做数据结构已经快恶心死了,于是让您帮她做当然,您天天做数据结构题,肯定也觉得恶心死了,不过可

爱即正义!所以这个题还是要做的~

Format

Input

第一行两个数n,m

之后一行一个长为n的字符串,代表每个人的编号

之后m行每行两个数l,r代表每次卓司妄想的区间

n,m<=60000

Output

m行,每行一个数表示答案

Samples

6 6
zzqzzq
1 6
2 4
3 4
2 3
4 5
1 1
16
4
2
2
3
1