#include <bits/stdc++.h>
using namespace std ;
#define MAXN 100005
#define mod 3
#define MAXM 500
#define LL long long int
int N,Q,C,X,Y,BS,NB,BLOCK[MAXM][3],LAZY[MAXM],F[MAXM],ORG[MAXN],BLOCKEND[MAXM],BLOCKSTART[MAXM],A[MAXN];
char str[MAXN] ;
LL ANS[3],ans,TEMP[3];
int getblock(int idx){
return ((idx-1)/BS + 1) ;
}
void buildSQRT(){
for(int i=1;i<=N;i++){
int block = getblock(i) ;
BLOCK[block][A[i]] ++ ;
if(BLOCKSTART[block] == 0)
BLOCKSTART[block] = i ;
BLOCKEND[block] = i ;
}
}
void update(int idx,int val){
val = val%mod ;
val = val - ORG[idx] ;
val += mod ;
val %= mod ;
ORG[idx] += val ;
ORG[idx] %= mod ;
int block = getblock(idx) ;
if(F[block]){
for(int i=BLOCKSTART[block];i<=BLOCKEND[block];i++){
A[i] = A[i]+LAZY[block] ;
A[i] %= mod ;
}
F[block] = 0;
LAZY[block] = 0;
}
for(int i=idx;i<=BLOCKEND[block];i++){
BLOCK[block][A[i]] -- ;
A[i] += val ;
A[i] %= mod ;
BLOCK[block][A[i]] ++ ;
}
for(int i=block+1;i<=NB;i++){
F[i] = 1;
LAZY[i] += val ;
LAZY[i] %= mod ;
TEMP[0] = TEMP[1] = TEMP[2] = 0 ;
TEMP[(val+0)%mod] = BLOCK[i][0] ;
TEMP[(val+1)%mod] = BLOCK[i][1] ;
TEMP[(val+2)%mod] = BLOCK[i][2] ;
BLOCK[i][0] = TEMP[0] ;
BLOCK[i][1] = TEMP[1] ;
BLOCK[i][2] = TEMP[2] ;
}
}
void query(int L,int R){
int block = getblock(L) ;
ANS[0] = ANS[1] = ANS[2] = 0;
if(F[block]){
for(int i=BLOCKSTART[block];i<=BLOCKEND[block];i++){
A[i] = A[i]+LAZY[block] ;
A[i] %= mod ;
}
F[block] = 0;
LAZY[block] = 0;
}
for(;L<=min(BLOCKEND[block],R);L++){
ANS[A[L]] ++ ;
}
block = getblock(R) ;
if(F[block]){
for(int i=BLOCKSTART[block];i<=BLOCKEND[block];i++){
A[i] = A[i]+LAZY[block] ;
A[i] %= mod ;
}
F[block] = 0;
LAZY[block] = 0;
}
for(;R>=max(BLOCKSTART[block],L);R--){
ANS[A[R]] ++ ;
}
if(L<=R){
for(int i=getblock(L);i<=getblock(R);i++){
ANS[0] += BLOCK[i][0] ;
ANS[1] += BLOCK[i][1] ;
ANS[2] += BLOCK[i][2] ;
}
}
}
int main(){
scanf("%d%d",&N,&Q) ;
scanf("%s",str+1) ;
for(int i=1;i<=N;i++){
A[i] = str[i] - '0' ;
A[i] += A[i-1] ;A[i] %= mod ;
ORG[i] = str[i] -'0' ;ORG[i] %= mod ;
}
BS = sqrt(N) ;
NB = (N/BS) + bool(N%BS) ;
buildSQRT() ;
while(Q--){
scanf("%d%d%d",&C,&X,&Y) ;
if(C == 1){
update(X,Y) ;
}else{
query(X,Y) ;
int val = (A[X-1]+LAZY[(X == 1 ? 0 : getblock(X-1))]);
val %= mod ;
TEMP[(0-val+mod)%mod] = ANS[0] ;
TEMP[(1-val+mod)%mod] = ANS[1] ;
TEMP[(2-val+mod)%mod] = ANS[2] ;
ANS[0] = TEMP[0] ;
ANS[1] = TEMP[1] ;
ANS[2] = TEMP[2] ;
ans = 0 ;
ans += (ANS[0]*(ANS[0]+1)/2) ;
ans += (ANS[1]*(ANS[1]-1)/2) ;
ans += (ANS[2]*(ANS[2]-1)/2) ;
printf("%lld\n",ans ) ;
}
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+IAp1c2luZyBuYW1lc3BhY2Ugc3RkIDsKIAojZGVmaW5lIE1BWE4gMTAwMDA1IAojZGVmaW5lIG1vZCAzCiNkZWZpbmUgTUFYTSA1MDAgCiNkZWZpbmUgTEwgbG9uZyBsb25nIGludCAKIAppbnQgTixRLEMsWCxZLEJTLE5CLEJMT0NLW01BWE1dWzNdLExBWllbTUFYTV0sRltNQVhNXSxPUkdbTUFYTl0sQkxPQ0tFTkRbTUFYTV0sQkxPQ0tTVEFSVFtNQVhNXSxBW01BWE5dOwpjaGFyIHN0cltNQVhOXSA7CkxMIEFOU1szXSxhbnMsVEVNUFszXTsKIAppbnQgZ2V0YmxvY2soaW50IGlkeCl7CglyZXR1cm4gKChpZHgtMSkvQlMgKyAxKSA7Cn0KIAogCnZvaWQgYnVpbGRTUVJUKCl7Cglmb3IoaW50IGk9MTtpPD1OO2krKyl7CgkJaW50IGJsb2NrID0gZ2V0YmxvY2soaSkgOwoJCUJMT0NLW2Jsb2NrXVtBW2ldXSArKyA7CgkJaWYoQkxPQ0tTVEFSVFtibG9ja10gPT0gMCkKCQkJQkxPQ0tTVEFSVFtibG9ja10gPSBpIDsKCQlCTE9DS0VORFtibG9ja10gPSBpIDsKCX0KfQogCiAKIAp2b2lkIHVwZGF0ZShpbnQgaWR4LGludCB2YWwpewogCiAKCXZhbCA9IHZhbCVtb2QgOwoJdmFsID0gdmFsIC0gT1JHW2lkeF0gOwoJdmFsICs9IG1vZCA7Cgl2YWwgJT0gbW9kIDsKCU9SR1tpZHhdICs9IHZhbCA7CglPUkdbaWR4XSAlPSBtb2QgOwoJCglpbnQgYmxvY2sgPSBnZXRibG9jayhpZHgpIDsKIAoJaWYoRltibG9ja10pewoJCWZvcihpbnQgaT1CTE9DS1NUQVJUW2Jsb2NrXTtpPD1CTE9DS0VORFtibG9ja107aSsrKXsKCQkJQVtpXSA9IEFbaV0rTEFaWVtibG9ja10gOwoJCQlBW2ldICU9IG1vZCA7CgkJfQoJCUZbYmxvY2tdID0gMDsKCQlMQVpZW2Jsb2NrXSA9IDA7Cgl9CiAKCWZvcihpbnQgaT1pZHg7aTw9QkxPQ0tFTkRbYmxvY2tdO2krKyl7CgkJQkxPQ0tbYmxvY2tdW0FbaV1dIC0tIDsKCQlBW2ldICs9IHZhbCA7CgkJQVtpXSAlPSBtb2QgOwoJCUJMT0NLW2Jsb2NrXVtBW2ldXSArKyA7Cgl9CiAKCWZvcihpbnQgaT1ibG9jaysxO2k8PU5CO2krKyl7CgkJRltpXSA9IDE7CgkJTEFaWVtpXSArPSB2YWwgOwoJCUxBWllbaV0gJT0gbW9kIDsKCQlURU1QWzBdID0gVEVNUFsxXSA9IFRFTVBbMl0gPSAwIDsJCgkJVEVNUFsodmFsKzApJW1vZF0gPSBCTE9DS1tpXVswXSA7CgkJVEVNUFsodmFsKzEpJW1vZF0gPSBCTE9DS1tpXVsxXSA7CgkJVEVNUFsodmFsKzIpJW1vZF0gPSBCTE9DS1tpXVsyXSA7CQkJCQkJCgkJQkxPQ0tbaV1bMF0gPSBURU1QWzBdIDsKCQlCTE9DS1tpXVsxXSA9IFRFTVBbMV0gOwoJCUJMT0NLW2ldWzJdID0gVEVNUFsyXSA7CQoJfQkJCgkKfQogCnZvaWQgcXVlcnkoaW50IEwsaW50IFIpewogCgkKCWludCBibG9jayA9IGdldGJsb2NrKEwpIDsKCUFOU1swXSA9IEFOU1sxXSA9IEFOU1syXSA9IDA7CiAKCWlmKEZbYmxvY2tdKXsKCQlmb3IoaW50IGk9QkxPQ0tTVEFSVFtibG9ja107aTw9QkxPQ0tFTkRbYmxvY2tdO2krKyl7CgkJCUFbaV0gPSBBW2ldK0xBWllbYmxvY2tdIDsKCQkJQVtpXSAlPSBtb2QgOwoJCX0KCQlGW2Jsb2NrXSA9IDA7CgkJTEFaWVtibG9ja10gPSAwOwoJfQoJCQoJZm9yKDtMPD1taW4oQkxPQ0tFTkRbYmxvY2tdLFIpO0wrKyl7CgkJQU5TW0FbTF1dICsrIDsKCX0KCWJsb2NrID0gZ2V0YmxvY2soUikgOwoJaWYoRltibG9ja10pewoJCWZvcihpbnQgaT1CTE9DS1NUQVJUW2Jsb2NrXTtpPD1CTE9DS0VORFtibG9ja107aSsrKXsKCQkJQVtpXSA9IEFbaV0rTEFaWVtibG9ja10gOwoJCQlBW2ldICU9IG1vZCA7CgkJfQoJCUZbYmxvY2tdID0gMDsKCQlMQVpZW2Jsb2NrXSA9IDA7Cgl9CiAKCWZvcig7Uj49bWF4KEJMT0NLU1RBUlRbYmxvY2tdLEwpO1ItLSl7CgkJQU5TW0FbUl1dICsrIDsKCX0KCWlmKEw8PVIpewkKCQlmb3IoaW50IGk9Z2V0YmxvY2soTCk7aTw9Z2V0YmxvY2soUik7aSsrKXsKCQkJQU5TWzBdICs9IEJMT0NLW2ldWzBdIDsKCQkJQU5TWzFdICs9IEJMT0NLW2ldWzFdIDsKCQkJQU5TWzJdICs9IEJMT0NLW2ldWzJdIDsKCQl9Cgl9Cn0KaW50IG1haW4oKXsKIAoJc2NhbmYoIiVkJWQiLCZOLCZRKSA7CglzY2FuZigiJXMiLHN0cisxKSA7Cglmb3IoaW50IGk9MTtpPD1OO2krKyl7CgkJQVtpXSA9IHN0cltpXSAtICcwJyA7CgkJQVtpXSArPSBBW2ktMV0gO0FbaV0gJT0gbW9kIDsKCQlPUkdbaV0gPSBzdHJbaV0gLScwJyA7T1JHW2ldICU9IG1vZCA7Cgl9CiAKCUJTID0gc3FydChOKSA7CglOQiA9IChOL0JTKSArIGJvb2woTiVCUykgOwogCglidWlsZFNRUlQoKSA7Cgl3aGlsZShRLS0pewogCgkJc2NhbmYoIiVkJWQlZCIsJkMsJlgsJlkpIDsKCQlpZihDID09IDEpewoJCQl1cGRhdGUoWCxZKSA7CgkJfWVsc2V7CgkJCXF1ZXJ5KFgsWSkgOwoJCQlpbnQgdmFsID0gKEFbWC0xXStMQVpZWyhYID09IDEgPyAwIDogZ2V0YmxvY2soWC0xKSldKTsKCQkJdmFsICU9IG1vZCA7CgkJCVRFTVBbKDAtdmFsK21vZCklbW9kXSA9IEFOU1swXSA7CgkJCVRFTVBbKDEtdmFsK21vZCklbW9kXSA9IEFOU1sxXSA7CgkJCVRFTVBbKDItdmFsK21vZCklbW9kXSA9IEFOU1syXSA7CgkJCUFOU1swXSA9IFRFTVBbMF0gOwoJCQlBTlNbMV0gPSBURU1QWzFdIDsKCQkJQU5TWzJdID0gVEVNUFsyXSA7CgkJCWFucyA9IDAgOwoJCQlhbnMgKz0gKEFOU1swXSooQU5TWzBdKzEpLzIpIDsKCQkJYW5zICs9IChBTlNbMV0qKEFOU1sxXS0xKS8yKSA7CgkJCWFucyArPSAoQU5TWzJdKihBTlNbMl0tMSkvMikgOwkJCQkKCQkJcHJpbnRmKCIlbGxkXG4iLGFucyApIDsKCQl9Cgl9CQkKCXJldHVybiAwOwp9