#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<algorithm>
#include<bitset>
#include<list>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<cmath>
#include<string>
#include<cstring>
#include<sstream>
#include<climits>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef set<int> si;
typedef map<string, int> msi;

#define S(x) scanf("%d",&x)
#define SD(x) scanf("%lf",&x)
#define SL(x) scanf("%lld",&x)
#define pb(x) push_back(x)
#define mp make_pair
#define F(i, a, b) for (int i = int(a); i < int(b); i++)
#define forit(it, a) for (it = (a).begin(); it != (a).end(); it++)
#define M(x,i) memset(x,i,sizeof(x))

/* -------------------CODE GOES HERE---------------------- */

int sol(string s){

    int t,i,a[555][555],p,cnt,j;
    
        F(i,0,555) F(j,0,555) a[i][j]=0;
	        p=s.length();
	        for(i=p-1;i>=0;i--) {
	            cnt=1;
	            a[i][i]=1;
	            if(i+1!=p){
	            if(s[i]==s[i+1])
	            {
	                cnt++;
	                a[i][i+1]=3;
	            }
	            else a[i][i+1]=2;
	            }
	            F(j,i+2,p){
	                if(s[i]==s[j])
	                {
	                    cnt++;
	                    cnt+=a[i+1][j-1];
	                }
	                a[i][j]=a[i+1][j]+cnt;
            	}
        	}
        
        return a[0][p-1];
}

int main(){

	int n,q,p,i,j,t;
	S(n); S(q);
	string s;
	cin>>s;

	while(q--){
		S(p);
		if(p == 1){
			S(i); S(j); S(t);
			//ignore :P
		}
		if(p == 2){
			S(i); S(j);
			cout<<sol(s.substr(i,j+1))<<endl;
		}
	}
}