RT

#include<bits/stdc++.h>
#include<map>
#include<vector>
#include<set>
using namespace std;
typedef long long ll;
const ll MAXN=1e6+5;
ll n,q;
struct node{
	ll id,t_l,t_r;
	string s;
}t[MAXN];
string op,Q;
ll L,R,cnt;
unordered_map<string,ll> mp;
ll trie[MAXN][2],tot;
vector<node> point[MAXN];
void insert(ll t_id){
	string str=t[t_id].s;
	ll now=0;
	for(int i=0;str[i];i++){
		ll E=str[i]-'0';
		if(!trie[now][E])trie[now][E]=++tot;
		now=trie[now][E];
	}
	point[now].push_back(t[t_id]);
	return;
}

ll l_col[MAXN<<2],r_col[MAXN<<2],_cnt[MAXN<<2],lazy[MAXN<<2];
void init(){
	memset(l_col,0,sizeof(l_col));
	memset(r_col,0,sizeof(r_col));
	for(int i=1;i<=n<<2;i++)_cnt[i]=1,lazy[i]=-1;
	return;
}
void push_up(ll id,ll L,ll R){
	l_col[id]=l_col[id<<1],r_col[id]=r_col[id<<1|1];
	_cnt[id]=_cnt[id<<1]+_cnt[id<<1|1]-(r_col[id<<1]==l_col[id<<1|1]);
	return;
}
void push_down(ll id,ll L,ll R){
	if(lazy[id]==-1)return;
	_cnt[id<<1]=_cnt[id<<1|1]=1;
	l_col[id<<1]=r_col[id<<1]=l_col[id<<1|1]=r_col[id<<1|1]=lazy[id];
	lazy[id]=-1;
	return;
} 
void assign(ll id,ll L,ll R,ll UL,ll UR,ll k){
	if(R<UL||L>UR)return;
	if(UL<=L&&R<=UR){
		lazy[id]=l_col[id]=r_col[id]=k;
		_cnt[id]=1;
		return;
	}
	ll mid=(L+R)>>1;
	push_down(id,L,R);
	assign(id<<1,L,mid,UL,UR,k);
	assign(id<<1|1,mid+1,R,UL,UR,k);
	push_up(id,L,R);
	return;
}
void opt(){
	ll len=Q.size();
	ll now=0;
	for(int i=0;i<len;i++){
		ll E=Q[i]-'0';
		if(!trie[now][E])break;
		now=trie[now][E];
		for(auto X:point[now]){
			assign(1,1,n,X.t_l,X.t_r,X.id);
		}
	}
	return;
}
ll query(ll id,ll L,ll R,ll QL,ll QR){
	if(R<QL||L>QR)return 0;
	if(QL<=L&&R<=QR)return _cnt[id];
	ll mid=(L+R)>>1;
	push_down(id,L,R);
	if(QR<=mid)return query(id<<1,L,mid,QL,QR);
	if(QL>mid)return query(id<<1|1,mid+1,R,QL,QR);
	return query(id<<1,L,mid,QL,QR)+query(id<<1|1,mid+1,R,QL,QR)-(r_col[id<<1]==l_col[id<<1|1]);
}
ll read(){
	ll x=0;char ch=getchar();
	while(!(ch>='0'&&ch<='9'))ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch-'0'),ch=getchar();
	return x;
}
int main(){
//	ios::sync_with_stdio(0);
//	cin.tie(0);
//	cout.tie(0);
	n=read(),q=read(); 
	for(int i=1;i<=n;i++){
		cin>>op>>Q;
		if(op=="Del")t[mp[Q]].t_r=i-1,mp[Q]=0;
		else t[++cnt].t_l=i,t[cnt].s=Q,mp[Q]=cnt;
	}
	for(int i=1;i<=cnt;i++)t[i].id=i,t[i].t_r=(t[i].t_r==0?n:t[i].t_r),insert(i);
//	cout<<"!\n";
	init();
//	cout<<"?\n";
	for(int i=1;i<=q;i++){
		assign(1,1,n,1,n,-1);
		cin>>Q;
		opt();
		L=read(),R=read();
		cout<<query(1,1,n,L,R)-1<<'\n';
	}
	return 0;
}