Description
小花梨有一个长度为𝑛且只包含小写字母的字符串。现在对其进行𝑞次询问。
每次询问字符串的一段区间[𝑙, 𝑟]，从[𝑙, 𝑟]区间内的所有子串中最多可以选出多少个字符串，
使得选出来的这些字符串存在一种排列方式满足相邻的两个字符串𝑎, 𝑏的最长公共后缀长度
大于等于𝑚𝑖𝑛(𝑠𝑡𝑟𝑙𝑒𝑛(𝑎), 𝑠𝑡𝑟𝑙𝑒𝑛(𝑏)) − 1。
Input
第一行输入两个正整数𝑛和𝑞，分别表示字符串长度和询问次数。
第二行为长度为𝑛的字符串。接下来𝑞行，每行两个正整数𝑙, 𝑟表示询问的区间。
(1 ≤ 𝑛 ≤ 10000,1 ≤ 𝑞 ≤ 10000,1 ≤ 𝑙 ≤ 𝑟 ≤ 𝑛)
Output
输出𝑞行，第𝑖行输出第𝑖次询问的答案
Example
Sample Input Sample Output
3 3
abc
1 1
1 2
1 3
1
3
6
Note
[1,1]内有1个子串：𝑎 ，存在排列𝑎满足要求，长度为1
[1,2]内有3个子串：𝑎, 𝑏, 𝑎𝑏，存在排列𝑎, 𝑎𝑏, 𝑏满足要求，长度为3
[1,3]内有6个子串：𝑎, 𝑏, 𝑐, 𝑎𝑏, 𝑏𝑐, 𝑎𝑏𝑐，存在排列𝑎𝑏, 𝑏, 𝑐, 𝑏𝑐, 𝑎𝑏𝑐, 𝑎满足要求，长度为6

对于询问[l,r]，(r-l+1)*(r-l+2)/2

#include <stdio.h>
#include<iostream>
#include<algorithm>
#include <string.h>
#define MAXN 10000 + 10
#define N 20
#define ll long long
using namespace std;
char a[20500];
int main()
{
    ll n,q;
    while(scanf("%lld %lld",&n,&q)!=EOF)
    {
        scanf("%s",a);
        ll l,r;
        for(int i=1;i<=q;i++)
        {
            scanf("%lld %lld",&l,&r);
            ll m;
            m=r-l+1;
            printf("%lld\n",m*(m+1)/2);
        }
    }
}
/*
5 10 5 15 10
1 2 3 4 5
*/