#include<bits/stdc++.h>
typedef int ll;
typedef unsigned long long ull;
typedef long double ld;
#define pii pair<ll,ll>
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define per(i,a,b) for(ll i=(a);i>=(b);--i)
using namespace std;
bool Mbe;
inline ll read(){
	ll x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	return x*f;
}
inline void write(ll x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
const ll N=5e5+9;
ll n,q,rev[N],a[N],bel[N],L[N],R[N],f[12],h[12],S;
struct M{
	ll a[12][12];
	void clear(){
		rep(i,0,11){
			rep(j,0,11)a[i][j]=1e7;
		}
	}
}blk[3005],trans[12];
M operator*(const M&a,const M&b){
	M c;c.clear();
	rep(k,0,11){
		rep(i,0,11){
			rep(j,0,11)c.a[i][j]=min(c.a[i][j],a.a[i][k]+b.a[k][j]);
		}
	}
	return c;
}
void Build(ll i){
	blk[i]=trans[a[L[i]]];
	rep(j,L[i]+1,R[i])blk[i]=blk[i]*trans[a[j]];
}
void Mul(ll*f,M g){
	rep(i,0,11)h[i]=1e7;
	rep(i,0,11){
		rep(j,0,11)h[j]=min(h[j],f[i]+g.a[i][j]);
	}
	rep(i,0,11)f[i]=h[i];
}
char s[N];
mt19937 rnd(time(0));
bool Med;
int main(){
	cerr<<fabs(&Med-&Mbe)/1048576.0<<"MB\n";
	n=read(),q=read();
	// n=500000,q=0;
	scanf("%s",s+1);
	// rep(i,1,n)s[i]=rnd()%26+'a';
	rev['d']=1,rev['o']=2;
	rev['r']=3,rev['e']=4;
	rev['m']=5,rev['i']=6;
	rev['f']=7,rev['a']=8;
	rev['s']=9;
	rev['l']=10;
	rev['t']=11;
	rep(i,0,11)trans[i].clear();
	rep(j,0,11){
		rep(i,0,11)trans[j].a[i][i]=1;
	}
	rep(j,1,11){
		trans[j].a[0][j]=0;
	}
	trans[2].a[1][0]=0;
	trans[4].a[3][0]=0;
	trans[6].a[5][0]=0;
	trans[8].a[7][0]=0;
	trans[2].a[9][0]=0;
	trans[8].a[10][0]=0;
	trans[6].a[11][0]=0;
	rep(i,1,n)a[i]=rev[s[i]];
	S=200;
	rep(i,1,n){
		bel[i]=(i-1)/S+1;
		if(!L[bel[i]])L[bel[i]]=i;
		R[bel[i]]=i;
	}
	rep(i,1,bel[n])Build(i);
	while(q--){
		char op[3];
		scanf("%s",op);
		if(op[0]=='?'){
			ll l=read(),r=read();
			rep(i,0,11)f[i]=1e7;
			f[0]=0;
			if(bel[l]==bel[r]){
				rep(i,l,r)Mul(f,trans[a[i]]);
			}
			else {
				rep(i,l,R[bel[l]])Mul(f,trans[a[i]]);
				rep(i,bel[l]+1,bel[r]-1)Mul(f,blk[i]);
				rep(i,L[bel[r]],r)Mul(f,trans[a[i]]);
			}
			write(f[0]),putchar('\n');
		}
		else {
			ll l=read(),r=read();
			scanf("%s",s+1);
			rep(i,l,r)a[i]=rev[s[i-l+1]];
			rep(i,bel[l],bel[r])Build(i);
		}
	}
	return 0;
}