\rt P6357

#include<bits/stdc++.h>
using namespace std;
int tag[2000001],cnt[2000001][10];
short rrr[250001];
int n,m;
string ansss;
inline int read() {
    int e=0;
    char ch;
    while(1) {
        ch=getchar();
        if(ch==' '||ch=='\n')
            break;
        e=(e<<3)+(e*2)+ch-'0';
    }
    return e;
}
inline void put(int a) {
    string b="";
    while(a) {
        b.push_back((char)(a%10+'0'));
        a/=10;
    }
    int len=b.size();
    for(int i=0;i<len/2;i++) swap(b[i],b[len-i-1]);
    ansss+=b;
    ansss+='\n';
}
inline void make(int i,int l,int r,int x,int y) {
    int a=i*2,b=i*2+1;
    if(l>=x&&r<=y) {
        tag[i]++;
        return;
    }
{
    if(tag[i]==0)
        ; 
    else {
    int c=0;
	tag[a]+=tag[i];
	tag[b]+=tag[i];
    cnt[c][(0+tag[i])%10]=cnt[i][0];
    cnt[c][(1+tag[i])%10]=cnt[i][1];
    cnt[c][(2+tag[i])%10]=cnt[i][2];
    cnt[c][(3+tag[i])%10]=cnt[i][3];
    cnt[c][(4+tag[i])%10]=cnt[i][4];
    cnt[c][(5+tag[i])%10]=cnt[i][5];
    cnt[c][(6+tag[i])%10]=cnt[i][6];
    cnt[c][(7+tag[i])%10]=cnt[i][7];
    cnt[c][(8+tag[i])%10]=cnt[i][8];
    cnt[c][(9+tag[i])%10]=cnt[i][9];
    cnt[i][0]=cnt[c][0];
    cnt[i][1]=cnt[c][1];
    cnt[i][2]=cnt[c][2];
    cnt[i][3]=cnt[c][3];
    cnt[i][4]=cnt[c][4];
    cnt[i][5]=cnt[c][5];
    cnt[i][6]=cnt[c][6];
    cnt[i][7]=cnt[c][7];
    cnt[i][8]=cnt[c][8];
    cnt[i][9]=cnt[c][9];
    tag[i]=0;
    }
}
    int mid=(l+r)>>1;
    if(y>=mid+1)
        make(b,mid+1,r,x,y);
    if(x<=mid)
        make(a,l,mid,x,y);
{
    if(tag[a]==0)
        ;
    else {
    int c=0;
	tag[a*2]+=tag[a];
	tag[a*2+1]+=tag[a];
    cnt[c][(0+tag[a])%10]=cnt[a][0];
    cnt[c][(1+tag[a])%10]=cnt[a][1];
    cnt[c][(2+tag[a])%10]=cnt[a][2];
    cnt[c][(3+tag[a])%10]=cnt[a][3];
    cnt[c][(4+tag[a])%10]=cnt[a][4];
    cnt[c][(5+tag[a])%10]=cnt[a][5];
    cnt[c][(6+tag[a])%10]=cnt[a][6];
    cnt[c][(7+tag[a])%10]=cnt[a][7];
    cnt[c][(8+tag[a])%10]=cnt[a][8];
    cnt[c][(9+tag[a])%10]=cnt[a][9];
    cnt[a][0]=cnt[c][0];
    cnt[a][1]=cnt[c][1];
    cnt[a][2]=cnt[c][2];
    cnt[a][3]=cnt[c][3];
    cnt[a][4]=cnt[c][4];
    cnt[a][5]=cnt[c][5];
    cnt[a][6]=cnt[c][6];
    cnt[a][7]=cnt[c][7];
    cnt[a][8]=cnt[c][8];
    cnt[a][9]=cnt[c][9];
    tag[a]=0;
    }
}
    {
    if(tag[b]==0)
        ;
    else {
    int c=0;
	tag[b*2]+=tag[b];
	tag[b*2+1]+=tag[b];
    cnt[c][(0+tag[b])%10]=cnt[b][0];
    cnt[c][(1+tag[b])%10]=cnt[b][1];
    cnt[c][(2+tag[b])%10]=cnt[b][2];
    cnt[c][(3+tag[b])%10]=cnt[b][3];
    cnt[c][(4+tag[b])%10]=cnt[b][4];
    cnt[c][(5+tag[b])%10]=cnt[b][5];
    cnt[c][(6+tag[b])%10]=cnt[b][6];
    cnt[c][(7+tag[b])%10]=cnt[b][7];
    cnt[c][(8+tag[b])%10]=cnt[b][8];
    cnt[c][(9+tag[b])%10]=cnt[b][9];
    cnt[b][0]=cnt[c][0];
    cnt[b][1]=cnt[c][1];
    cnt[b][2]=cnt[c][2];
    cnt[b][3]=cnt[c][3];
    cnt[b][4]=cnt[c][4];
    cnt[b][5]=cnt[c][5];
    cnt[b][6]=cnt[c][6];
    cnt[b][7]=cnt[c][7];
    cnt[b][8]=cnt[c][8];
    cnt[b][9]=cnt[c][9];
    tag[b]=0;
}}
    cnt[i][1]=cnt[a][1]+cnt[b][1];
    cnt[i][2]=cnt[a][2]+cnt[b][2];
    cnt[i][3]=cnt[a][3]+cnt[b][3];
    cnt[i][4]=cnt[a][4]+cnt[b][4];
    cnt[i][5]=cnt[a][5]+cnt[b][5];
    cnt[i][6]=cnt[a][6]+cnt[b][6];
    cnt[i][7]=cnt[a][7]+cnt[b][7];
    cnt[i][8]=cnt[a][8]+cnt[b][8];
    cnt[i][9]=cnt[a][9]+cnt[b][9];
    cnt[i][0]=cnt[a][0]+cnt[b][0];
}
inline int ans(int i,int l,int r,int x,int y) {
    int a=i*2,b=i*2+1;
    {
    if(tag[i]==0)
        ; 
    else {
    int c=0;
	tag[a]+=tag[i];
	tag[b]+=tag[i];
    cnt[c][(0+tag[i])%10]=cnt[i][0];
    cnt[c][(1+tag[i])%10]=cnt[i][1];
    cnt[c][(2+tag[i])%10]=cnt[i][2];
    cnt[c][(3+tag[i])%10]=cnt[i][3];
    cnt[c][(4+tag[i])%10]=cnt[i][4];
    cnt[c][(5+tag[i])%10]=cnt[i][5];
    cnt[c][(6+tag[i])%10]=cnt[i][6];
    cnt[c][(7+tag[i])%10]=cnt[i][7];
    cnt[c][(8+tag[i])%10]=cnt[i][8];
    cnt[c][(9+tag[i])%10]=cnt[i][9];
    cnt[i][0]=cnt[c][0];
    cnt[i][1]=cnt[c][1];
    cnt[i][2]=cnt[c][2];
    cnt[i][3]=cnt[c][3];
    cnt[i][4]=cnt[c][4];
    cnt[i][5]=cnt[c][5];
    cnt[i][6]=cnt[c][6];
    cnt[i][7]=cnt[c][7];
    cnt[i][8]=cnt[c][8];
    cnt[i][9]=cnt[c][9];
    tag[i]=0;
    }
}
    if(l>=x&&r<=y) {
        int sum=0;
        for(short j=1;j<=9;j++)
            sum+=j*cnt[i][j];
        return sum;
    }
    int sum=0;
    int mid=(l+r)>>1;
    if(y>=mid+1)
        sum+=ans(b,mid+1,r,x,y);
    if(x<=mid)
        sum+=ans(a,l,mid,x,y);
    return sum;
}
inline void build(int i,int l,int r) {
    int a=i*2,b=i*2+1;
    if(l==r) {
        cnt[i][rrr[l]]++;
        return;
    }
    int mid=(l+r)>>1;
    build(i*2,l,mid);
    build(i*2+1,mid+1,r);
    cnt[i][1]=cnt[a][1]+cnt[b][1];
    cnt[i][2]=cnt[a][2]+cnt[b][2];
    cnt[i][3]=cnt[a][3]+cnt[b][3];
    cnt[i][4]=cnt[a][4]+cnt[b][4];
    cnt[i][5]=cnt[a][5]+cnt[b][5];
    cnt[i][6]=cnt[a][6]+cnt[b][6];
    cnt[i][7]=cnt[a][7]+cnt[b][7];
    cnt[i][8]=cnt[a][8]+cnt[b][8];
    cnt[i][9]=cnt[a][9]+cnt[b][9];
    cnt[i][0]=cnt[a][0]+cnt[b][0];
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    n=read(),m=read();
    char ttt;
    for(int i=1;i<=n;i++) {
        ttt=getchar();
        rrr[i]=ttt-'0';
    }
    getchar();
    build(1,1,n);
    while(m--) {
        int l,r;
        l=read();
        if(m==0)
            cin>>r;
        else
            r=read();
        put(ans(1,1,n,l,r));
        make(1,1,n,l,r);
    }
    int len=ansss.size();
    for(int i=0;i<len;i++)
        putchar(ansss[i]);
}