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 JAVA):

Solution:
import java.io.*;import java.util.*;import java.math.*;import static java.lang.Math.*;import static java.lang
.Integer.*;import static java.lang.Long.*;import static java.util.Map.*;import static java.util.Arrays.*;
import static java.lang.System.*;
public class Main
{
    public void tq()throws Exception
    {
        st=new StringTokenizer(bq.readLine());
        int tq=1;
        sb=new StringBuilder(1000000);
        o:
        while(tq-->0)
        {
            int n=i();
            int q=i();
            String s=s();
            char ar[]=s.toCharArray();
            int r[][]=new int[n][26];
            int t[]=new int[26];
            for(int x=0;x<n;x++)
            {
                int tt[]=new int[26];
                t[ar[x]-'a']++;
                for(int y=0;y<26;y++)tt[y]=t[y];
                r[x]=tt;
            }
            for(int x=0;x<q;x++)
            {
                int a=i()-2;
                int b=i()-1;
                int tt[]=new int[26];
                for(int y=0;y<26;y++)tt[y]=r[b][y];
                if(a>-1)for(int xa=0;xa<26;xa++)tt[xa]-=r[a][xa];
                long c=0l;
                for(int xa=0;xa<26;xa++)c+=(xa+1)*tt[xa];
                sl(c);
            }
        }
        p(sb);
    }

    long mod=1000000007l;int max=Integer.MAX_VALUE,min=Integer.MIN_VALUE;long maxl=Long.MAX_VALUE, minl=Long.
        MIN_VALUE;BufferedReader bq=new BufferedReader(new InputStreamReader(in));StringTokenizer st;
        StringBuilder sb;public static void main(String[] a)throws Exception{new Main().tq();}int[] so(int ar[])
    {Integer r[]=new Integer[ar.length];for(int x=0;x<ar.length;x++)r[x]=ar[x];sort(r);for(int x=0;x<ar.length;
        x++)ar[x]=r[x];return ar;}long[] so(long ar[]){Long r[]=new Long[ar.length];for(int x=0;x<ar.length;x++)
            r[x]=ar[x];sort(r);for(int x=0;x<ar.length;x++)ar[x]=r[x];return ar;}char[] so(char ar[]) {Character
        r[]=new Character[ar.length];for(int x=0;x<ar.length;x++)r[x]=ar[x];sort(r);for(int x=0;x<ar.length;x++)
            ar[x]=r[x];return ar;}void s(String s){sb.append(s);}void s(int s){sb.append(s);}void s(long s){sb.
        append(s);}void s(char s){sb.append(s);}void s(double s){sb.append(s);}void ss(){sb.append(' ');}void sl
    (String s){sb.append(s);sb.append("\n");}void sl(int s){sb.append(s);sb.append("\n");}void sl(long s){sb
        .append(s);sb.append("\n");}void sl(char s) {sb.append(s);sb.append("\n");}void sl(double s){sb.append(s)
    ;sb.append("\n");}void sl(){sb.append("\n");}
    int l(int v){return 31-numberOfLeadingZeros(v);}long l(long v){return 63-numberOfLeadingZeros(v);}int sq
        (int a){return (int)sqrt(a);}long sq(long a){return (long)sqrt(a);}long gcd(long a,long b){while(b>0l)
        {long c=a%b;a=b;b=c;}return a;}int gcd(int a,int b){while(b>0){int c=a%b;a=b;b=c;}return a;}boolean pa
        (String s,int i,int j){while(i<j)if(s.charAt(i++)!=s.charAt(j--))return false;return true;}boolean[] si
        (int n) {boolean bo[]=new boolean[n+1];bo[0]=true;bo[1]=true;for(int x=4;x<=n;x+=2)bo[x]=true;
            for(int x=3;x*x<=n;x+=2){if(!bo[x]){int vv=(x<<1);for(int y=x*x;y<=n;y+=vv)bo[y]=true;}}return bo;}
    long mul(long a,long b,long m) {long r=1l;a%=m;while(b>0){if((b&1)==1) r=(r*a)%m;b>>=1;a=(a*a)%m;}return r;}
    int i()throws IOException{if(!st.hasMoreTokens())st=new StringTokenizer(bq.readLine());return
            parseInt(st.nextToken());}long l()throws IOException{if(!st.hasMoreTokens())st=new StringTokenizer
        (bq.readLine());return parseLong(st.nextToken());}String s()throws IOException {if
    (!st.hasMoreTokens())st=new StringTokenizer(bq.readLine());return st.nextToken();}double d()throws
        IOException{if(!st.hasMoreTokens())st=new StringTokenizer(bq.readLine());return Double.parseDouble
        (st.nextToken());}void p(Object p){out.print(p);}void p(String p){out.print(p);}void p
        (int p){out.print(p);}void p(double p){out.print(p);}void p(long p){out.print(p);}
    void p(char p){out.print(p);}void p(boolean p){out.print(p);}void pl(Object p){out.
        println(p);}void pl(String p){out.println(p);}void pl(int p){out.println(p);}void pl
        (char p){out.println(p);}void pl(double p){out.println(p);}void pl(long p){out.
        println(p);}void pl(boolean p){out.println(p);}void pl(){out.println();}void s(int a[])
    {for(int e:a){sb.append(e);sb.append(' ');}sb.append("\n");}void s(long a[]){for(long e:a){sb.append(e);
        sb.append(' ');}sb.append("\n");}void s(int ar[][]){for(int a[]:ar){for(int e:a){sb.append(e);
            sb.append(' ');}sb.append("\n");}}void s(char a[]){for(char e:a){sb.append(e);sb.append(' ');}
    sb.append("\n");}void s(char ar[][]){for(char a[]:ar){for(char e:a){sb.append(e);sb.append(' ');}
    sb.append("\n");}}int[] ari(int n)throws IOException {int ar[]=new int[n];if(!st.hasMoreTokens())
        st=new StringTokenizer(bq.readLine());for(int x=0;x<n;x++)ar[x]=parseInt(st.nextToken());
        return ar;}int[][] ari(int n,int m)throws IOException {int ar[][]=new int[n][m];for(int x=0;x<n;x++){if
    (!st.hasMoreTokens())st=new StringTokenizer(bq.readLine());for(int y=0;y<m;y++)ar[x][y]=parseInt(st.
        nextToken());}return ar;}long[] arl(int n)throws IOException {long ar[]=new long[n];
            if(!st.hasMoreTokens()) st=new StringTokenizer(bq.readLine());for(int x=0;x<n;x++)ar[x]=
            parseLong(st.nextToken());return ar;}long[][] arl(int n,int m)throws IOException {long ar[][]
        =new long[n][m];for(int x=0;x<n;x++) {if(!st.hasMoreTokens()) st=new StringTokenizer(bq.readLine());
            for(int y=0;y<m;y++)ar[x][y] =parseLong(st.nextToken());}return ar;}String[] ars(int n)throws
        IOException {String ar[] =new String[n];if(!st.hasMoreTokens())st=new StringTokenizer(bq.readLine());
            for(int x=0;x<n;x++)ar[x]=st.nextToken();return ar;}double[] ard(int n)throws IOException {double ar[]
        =new double[n];if(!st.hasMoreTokens())st=new StringTokenizer(bq.readLine());for(int x=0;x<n;x++)ar[x]=
        Double.parseDouble(st.nextToken());return ar;}double[][] ard(int n,int m)throws IOException {double
        ar[][]=new double[n][m];for(int x=0;x<n;x++) {if(!st.hasMoreTokens())st=new StringTokenizer(bq.readLine())
        ;for(int y=0;y<m;y++) ar[x][y]=Double.parseDouble(st.nextToken());}return ar;}char[] arc(int n)throws
        IOException{char ar[]=new char[n];if(!st.hasMoreTokens())st=new StringTokenizer(bq.readLine());for
        (int x=0;x<n;x++)ar[x]=st.nextToken().charAt(0);return ar;}char[][] arc(int n,int m)throws IOException
        {char ar[][]=new char[n][m];for(int x=0;x<n;x++){String s=bq.readLine();for(int y=0;y<m;y++)ar[x][y]
                =s.charAt(y);}return ar;}void p(int ar[]){StringBuilder sb=new StringBuilder(2*ar.length);for
    (int a:ar){sb.append(a);sb.append(' ');}out.println(sb);}void p(int ar[][]){StringBuilder sb=new
        StringBuilder(2*ar.length*ar[0].length);for(int a[]:ar){for(int aa:a){sb.append(aa);sb.append(' ');}
    sb.append("\n");}p(sb);}void p(long ar[]){StringBuilder sb=new StringBuilder(2*ar.length);for(long a:ar){
        sb.append(a);sb.append(' ');}out.println(sb);}void p(long ar[][]){StringBuilder sb=new
        StringBuilder(2*ar.length*ar[0].length);for(long a[]:ar){for(long aa:a){sb.append(aa);sb.append(' ');}
    sb.append("\n");}p(sb);}void p(String ar[]){int c=0;for(String s:ar)c+=s.length()+1;StringBuilder sb=new
        StringBuilder(c);for(String a:ar){sb.append(a);sb.append(' ');}out.println(sb);}void p(
                double ar[]){StringBuilder sb=new StringBuilder(2*ar.length);for(double a:ar){sb.append(a);
                    sb.append(' ');}out.println(sb);}void p(double ar[][]){StringBuilder sb=new
        StringBuilder(2*ar.length*ar[0].length);for(double a[]:ar){for(double aa:a){sb.append(aa);sb.append(' ')
    ;}sb.append("\n");}p(sb);}void p(char ar[]){StringBuilder sb=new StringBuilder(2*ar.length);for(char aa:ar)
    {sb.append(aa);sb.append(' ');}out.println(sb);}void p(char ar[][]){StringBuilder sb=new StringBuilder
        (2*ar.length*ar[0].length);for(char a[]:ar){for(char aa:a){sb.append(aa);sb.append(' ');}sb.append("\n")
    ;}p(sb);}
}