#include<bits/stdc++.h>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define memo(a,v) memset(a,v,sizeof(a))
#define pb push_back
#define all(a) a.begin(),a.end()
#define eps (1e-9)
#define inf (1<<29)
#define i64 long long
#define u64 unsigned i64
#define AIN(a,b,c) assert(a<=b && b<=c)
#define MAXN 100000

typedef pair<int,i64> pii;

char a[MAXN+5];
int n;
i64 S[MAXN+5];

struct node{
    i64 cnt,pref[3],suff[3];
    int full;
    node(){
        cnt = 0;
        full = 0;
        memset(pref,0,sizeof(pref));
        memset(suff,0,sizeof(suff));
    }
}T[MAXN<<2];

void build(int lf,int rt,int idx){
    if(lf==rt){
        int y = a[lf-1] - '0';
        AIN(0,y,9);
        T[idx].cnt = y % 3 ==0?1:0;
        T[idx].full = y%3;
        for(int i = 0;i<3;i++){
            T[idx].pref[i] = T[idx].suff[i] = 0;
        }
        T[idx].pref[y%3] = 1;
        T[idx].suff[y%3] = 1;
        return;
    }
    int mid = (lf + rt) / 2;
    build(lf,mid,idx*2);
    build(mid+1,rt,idx*2 + 1);
    node &ret = T[idx], &r1 = T[idx*2], &r2 = T[idx*2+1];
    ret.cnt = r1.cnt + r2.cnt;
    for(int i = 0;i<3;i++){
        ret.cnt+= r1.suff[i]*r2.pref[(3-i)%3];
        ret.pref [i] = r1.pref [i] + r2.pref[(3 + i - r1.full)%3];
        ret.suff[i] = r2.suff[i] + r1.suff[(3 + i -r2.full)%3];
    }
    ret.full = (r1.full + r2.full)%3;
}
node query(int lf,int rt,int idx,int x,int y){
    if(lf>=x && rt<=y){
        return T[idx];
    }
    int mid = (lf + rt) / 2;
    node r1 = node(),r2 = node();
    if(x<=mid)
        r1 = query(lf,mid,idx*2,x,y);
    if(y>mid)
        r2 = query(mid+1,rt,idx*2 + 1,x,y);
    node ret= node();
    ret.cnt = r1.cnt + r2.cnt;
    for(int i = 0;i<3;i++){
        ret.cnt+= r1.suff[i]*r2.pref[(3-i)%3];
        ret.pref [i] = r1.pref [i] + r2.pref[(3 + i - r1.full)%3];
        ret.suff[i] = r2.suff[i] + r1.suff[(3 + i -r2.full)%3];
    }
    ret.full = (r1.full + r2.full)%3;
    return ret;
}
void update(int lf,int rt,int idx,int x,int y){
    if(lf==x && rt == x){
        T[idx].cnt = y % 3 ==0?1:0;
        T[idx].full = y%3;
        for(int i = 0;i<3;i++){
            T[idx].pref[i] = T[idx].suff[i] = 0;
        }
        T[idx].pref[y%3] = 1;
        T[idx].suff[y%3] = 1;
        return;
    }
    int mid = (lf + rt) / 2;
    if(x<=mid)
        update(lf,mid,idx*2,x,y);
    else
        update(mid+1,rt,idx*2 + 1,x,y);
    node &ret = T[idx], &r1 = T[idx*2], &r2 = T[idx*2+1];
    ret.cnt = r1.cnt + r2.cnt;
    for(int i = 0;i<3;i++){
        ret.cnt+= r1.suff[i]*r2.pref[(3-i)%3];
        ret.pref [i] = r1.pref [i] + r2.pref[(3 + i - r1.full)%3];
        ret.suff[i] = r2.suff[i] + r1.suff[(3 + i -r2.full)%3];
    }
    ret.full = (r1.full + r2.full)%3;
}
int main(){
    i64 ans,cnt;
    int i,m,t,x,y;
    scanf("%d %d",&n,&m);
    AIN(1,n,MAXN);
    AIN(1,m,MAXN);
    scanf("%s",a);
    assert(strlen(a) == n);
    build(1,n,1);
    while(m--){
        scanf("%d %d %d",&t,&x,&y);
        AIN(1,t,2);
        if(t == 1){
            AIN(1,x,n);
            AIN(0,y,9);
            update(1,n,1,x,y);
        }
        else{
            AIN(1,x,y);
            AIN(x,y,n);
            printf("%lld\n",query(1,n,1,x,y).cnt);
        }
    }
	return 0;
}