Problem: Petya once wrote a sad love song and shared it to Vasya. The song is a string consisting of lowercase English letters. Vasya made up q questions about this song. Each question is about a subsegment of the song starting from the l-th letter to the r-th letter. Vasya considers a substring made up from characters on this segment and repeats each letter in the subsegment k times, where k is the index of the corresponding letter in the alphabet. For example, if the question is about the substring "abbcb", then Vasya repeats letter 'a' once, each of the letters 'b' twice, letter 'c" three times, so that the resulting string is "abbbbcccbb", its length is 10. Vasya is interested about the length of the resulting string.

Help Petya find the length of each string obtained by Vasya.

Input

The first line contains two integers n and q (1≤ n≤ 100 000, 1≤ q ≤ 100 000) — the length of the song and the number of questions. 

The second line contains one string s — the song, consisting of n lowercase letters of English letters.

Vasya's questions are contained in the next q lines. Each line contains two integers l and r (1 ≤ l ≤ r ≤ n) — the bounds of the question.

Output

Print q lines: for each question print the length of the string obtained by Vasya.

Examples

Input


7 3
abacaba
1 3
2 5
1 7


Output


4
7
11


Input


7 4
abbabaa
1 3
5 7
6 6
2 4


Output


5
4
1
5


Input


13 7
sonoshikumiwo
1 5
2 10
7 7
1 13
4 8
2 5
3 9


Output


82
125
9
191
62
63
97

Note

In the first example Vasya is interested in three questions. In the first question Vasya considers the substring "aba", that transforms to "abba", so the answer is equal to 4. In the second question Vasya considers "baca", that transforms to "bbaccca", so the answer is 7. In the third question Vasya considers the string "abacaba",that transforms to "abbacccabba" of length 11.

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
#include<string>
using namespace std;


typedef long long ll;
typedef vector<ll> vi;
typedef vector<int> vin;
typedef vector<pair<ll, ll>> vll;
typedef vector<pair<int, int>> vii;
#define endl "\n"
#define pb push_back
#define fp(i,a,b) for(int i=a;i<b;++i)
#define fq(i,a,b) for(int i=a;i<=b;++i)
#define fst ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define all(a) a.begin(),a.end()
#define p11 cout<<"YES"<<endl
#define p00 cout<<"NO"<<endl
#define read(x) for(auto &i:x) cin>>i;
#define print(x) for(auto i:x) cout<<i<<" "; cout<<endl;
#define MOD 1e9+7
const int HIGHST = 1e5;


ll mod_pow(ll a, ll n, ll mod)  //(a^n)%mod
{   ll res = 1;
    while (n) {
        if (n & 1) res = (res * a) % mod; n /= 2; a = (a * a) % mod;
    }
    return res;
}

void sol()
{

    ll n, m;
    cin >> n >> m;
    vi v(n);
    //read(v);

    unordered_map<ll, ll> mp;


    for (ll i = 0; i < n; ++i)
    {
        ll x; cin >> x;
        v[i] = x % m;
        mp[x % m]++;
    }

    ll cnt = 0;

// print(v);

    if (mp[0] > 0)cnt = 1;

    ll kk;
    if (m % 2 == 0)
        kk = m / 2;
    else
        kk = m / 2 - 1;
    //for(ll i=1;i<=(m+1)/2 && i<m;++i)
    for (ll i = 1; i <= kk; ++i)
    {

        //cout<<i<<" "<<cnt<<endl;
        if (i == m - i)
        {
            if (mp[i] != 0)
                cnt += 1;
            continue;
        }
        if ( mp[i] == 0 || mp[m - i] == 0)
        {
            if (mp[i] != 0)
            {
                cnt += ((i + m - 1) / m);
            } else
            {
                cnt += (((m - i) + m - 1) / m);
            }
            continue;
            cnt += (mp[i] + mp[m - i] + 1) / 2;
            mp[i] = mp[m - i] = 0;
            continue;
        }

        ll tmp = min(mp[i], mp[i - 1]);
        if (abs(mp[i] - mp[m - i]) == 1)tmp++;
        mp[i] = max(0ll, mp[i] - tmp - 1);
        mp[m - i] = max(0ll, mp[m - i] - tmp - 1);
        cnt += tmp + mp[i] + mp[m - i];


    }

    cout << cnt;




}


long long gcd(long long int a, long long int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

long long lcm(int a, int b)
{
    return (a / gcd(a, b)) * b;
}
void fpar(int arr1[], int arr2[], int n,
          int m, int x)
{
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (arr1[i] + arr2[j] == x)
                cout << arr1[i] << " " << arr2[j] << endl;
}




int maxSubArraySum(vi a, int size)
{
    int max_so_far = INT_MIN, max_ending_here = 0;

    for (int i = 0; i < size; i++)
    {
        max_ending_here = max_ending_here + a[i];
        if (max_so_far < max_ending_here)
            max_so_far = max_ending_here;

        if (max_ending_here < 0)
            max_ending_here = 0;
    }
    return max_so_far;
}

int maxSum(vi arr, int n, int k)
{
    // k must be greater
    if (n < k)
    {
        cout << "value11initid";
        return -1;
    }

    int res = 0;
    for (int i = 0; i < k; i++)
        res += arr[i];


    int curr_sum = res;
    for (int i = k; i < n; i++)
    {
        curr_sum += arr[i] - arr[i - k];
        res = max(res, curr_sum);
    }

    return res;
}

void showpq(priority_queue<ll > gq)
{
    priority_queue<ll> g = gq;
    while (!g.empty()) {
        cout << '\t' << g.top();
        g.pop();
    }
    cout << '\n';
}

ll hel(string s, ll i, ll k)
{
    ll n = s.size();
    ll m = min(i + k - 1, n - 1);
    for (; m >= i; --m)
    {
        if (s[m] == '*')return m;
    }
    return -1;

}
void getit()
{
    ll dssfds;
    return;
}
ll dffdsf12sda;
int dsd12sdssdsds;
bool ffffds;
ll dfdffdqweoo;
void findNumbers(int arr[], int n)
{
    int num[n];
    int b_minus_a = arr[n - 1] - arr[1];

    // b is calculated here
    num[1] = (arr[0] + b_minus_a) / 2;

    // a is calculated here
    num[0] = arr[0] - num[1];


    for (int i = 1; i <= (n - 2); i++)
        num[i + 1] = arr[i] - num[0];

    // cout << "Numbers are: ";
    for (int i = 0; i < n; i++)
        cout << num[i] << " ";
}

ll cl(ll x, ll y)
{
    return (x + y - 1) / y;
}

ll factorial(ll n)
{
    ll res = 1, i;
    for (i = 2; i <= n; i++)
        res  = (res * i) ;
    return res;
}


ll findlen(long long n)
{
    ll count = 0;
    while (n != 0)
    {
        n = n / 10;
        ++count;
    }
    return count;
}

int countdig(long long n)
{
    int count = 0;
    while (n != 0)
    {
        n = n / 10;
        ++count;
    }
    return count;
}

ll finggiiutesp(vector<ll> arr)
{
    ll n = (ll)arr.size();

    unordered_map<ll, ll> map;
    for (ll i = 0; i < n; i++)
        map[arr[i] - i]++;
    ll res = 0;
    for (auto x : map) {
        ll cnt = x.second;
        res += ((cnt * (cnt - 1)) / 2);
    }

    return res;
}


ll countunsetbits(ll n)
{
    ll count = 0;

    for (ll x = 1; x <= n; x = x << 1)
        if ((x & n) == 0)
            count++;

    return count;
}

ll fact(ll n);

ll nCr(ll n, ll r)
{
    return fact(n) / (fact(r) * fact(n - r));
}

// Returns factorial of n
ll fact(ll n)
{
    ll res = 1;
    for (ll i = 2; i <= n; i++)
        res = res * i;
    return res;
}

void modify(string& s)
{
    int n = s.size();

    int i = 0;
    while (i < n)
    {
        int j = i;
        while (s[i] != '?')
        {
            i++;
        }
        int ln = j - i + 1;

    }
}
vector<ll> getPrimeFact(ll a)
{
    vector<ll> res;
    if (a % 2 == 0)
        res.push_back(2);
    while (a % 2 == 0)
    {
        a /= 2;
        // res.insert(2);
    }
    ll till = sqrt(a);
    for (int i = 3; i <= till; i += 2)
    {
        if (a % i == 0)
            res.push_back(i);
        while (a % i == 0)
        {
            a /= i;
            // res.insert(i);
        }
    }
    if (a > 2)
        res.push_back(a);
    return res;
}
bool checkPrimeComb(ll mn, vector<ll> primes)
{
    ll x = 0;
    bool f = 0;
    for (auto p : primes)
    {
        f = 0;
        while (mn % p == 0)
        {
            mn /= p; f = 1;
        }
        x += f;
        if (x > 1)return true;
    }
    return x > 1;
}
ll getCountPrimeComb(vector<ll> primes, ll num)
{
    set<ll> st;

    for (auto it : primes)
        st.insert(it);
    // st.insert(A);
    // st.insert(B);
    // st.insert(C);
    vector<ll> res;
    ll cnt = 0;
    ll mn = 1;
    while (mn <= num)
    {
        mn = (*st.begin());
        st.erase(st.begin());

        if (checkPrimeComb(mn, primes))
        {
            res.push_back(mn);
            cnt++;
        }
        for (auto it : primes)
            st.insert(it * mn);
        // st.insert(mn * A);
        // st.insert(mn * B);
        // st.insert(mn * C);
    }
    print(res);
    return cnt;
}

string func(string s1, string s2) {
    for (int i = 0; i < s1.size(); i++) {
        if (s1[i] < s2[i])
            return s1;
        else if (s1[i] > s2[i])
            return s2;
    }
    return s1;
}
string string1(string s, int sz) {
    string st;
    for (int i = 0; i < sz; i++)
        st += s[i % s.size()];
    return st;
}




void sol22()
{
    ll n, q;
    cin >> n >> q;
    string s;
    cin >> s;

    vector<vector<ll>> v(27, vector<ll>(n + 1));
    for (ll i = 0; i < n; ++i)
    {
        v[s[i] - 'a'][i + 1] = 1;
    }
    // make prefix
    for (ll i = 0; i < 26; ++i)
    {
        for (ll j = 1; j <= n; ++j)
        {
            v[i][j] += v[i][j - 1];
        }
    }
    // cout << "ok" << endl;
    // for (auto i : v)
    // {
    //     for (auto j : i)
    //         cout << j << " ";
    //     cout << endl;
    // }

    // cout << v.size() << "  " << v[0].size() << endl;
    vi final;
    // cout << v[1][1] << " dskds " << endl;

    while (q--)
    {
        int x, y;
        cin >> x >> y;
        // x--;
        // y--;

        ll res = 0;
        for (int t = 0; t < 26; ++t)
        {
//
            // cout << t << "  " << x << " " << y << endl;
            // cout << v[(int)t][(int)(x - 1)] - v[i][x - 1] << endl;
            res += (t + 1ll) * (v[(int)t][(int)y] - v[(int)t][(int)(x - 1)]);
        }
        final.push_back(res);

    }
    for (auto ele : final)
        cout << ele << endl;



    /*
    ll n, x, t;
    cin >> n >> x >> t;

    ll ii = t + x;
    ll p = ii / x; //p


    while (p * x <= t + x)
    {
        p++;
    }
    p--;

    ll m = (n * x - t) / x;

    while (t + m * x <= n * x)
    {
        m++;
    }
    m--;

    // getsum(p) - getsum(m);
    cout << p << " " << m << endl;
    */

}




int main() {

//     // fst;
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    // getit();
    // getit();


    // print(allsum);
    ll t = 1;
    // cin >> t;

    // cout << t << "    ";
    for (ll ppp = 1; ppp <= t; ++ppp)
    {
        // cout<<"Case "<<i<<": ";
        // getit();
        // bool cdwnur443333;
        sol22();
        // cout << endl;
    }

    return 0;
}