#include <iostream>
#include <cstring> 
#include <map>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
#include <set>
// #include <bits/stdc++.h>

// #define int long long
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rof(i,a,b) for(int i=(a);i>=(b);i--)
#define Grf(it,u,to) for(int it=he[u],to;(to=e[it],it);it=nxt[it]) 
#define In __inline 
#define OP operator
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
namespace Mine {
	// mt19937_64 wql(514);
	In int read() {
		ll x=1,a=0;
		char ch=getchar();
		while(ch>'9' || ch<'0') x=(ch=='-')?-1:x,ch=getchar();
		while(ch>='0' && ch<='9') a=(a<<1)+(a<<3)+(ch-'0'),ch=getchar();
		return a*x;
	} const int N=5e5+100;
	char ch[N];int n,m,X,fa[N],f[N][21],dep[N];
	
	
	bool No1=1;
	
	In int lca(int x,int y) {
		if(dep[x]<dep[y]) swap(x,y);
		Rof(i,20,0) if(dep[f[x][i]]>=dep[y]) x=f[x][i];
		if(x==y) return x;
		Rof(i,20,0) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
		return f[x][0];
	} int he[N],nxt[N],cf[N],idx=1,e[N];
	void adde(int a,int b,int c) {
		e[++idx]=b,cf[idx]=c,nxt[idx]=he[a];he[a]=idx;
	}
	namespace sol {
		namespace Mine {
			// mt19937_64 wql(514);
			In ll read() {
				ll x=1,a=0;
				char ch=getchar();
				while(ch>'9' || ch<'0') x=(ch=='-')?-1:x,ch=getchar();
				while(ch>='0' && ch<='9') a=(a<<1)+(a<<3)+(ch-'0'),ch=getchar();
				return a*x;
			} const int N=5e5+100;
			struct ACAM {
				int son[N][11],fail[N],idx=0,tr[N],dfn[N],ed[N],tot;
				vector<int> fs[N];
				void dfs(int u) {
					dfn[u]=++tot; for(int to:fs[u]) {dfs(to);} ed[u]=tot;
				} void build() {
					queue<int> q; For(i,0,9) if(son[0][i]) q.push(son[0][i]);
					while(q.size()) { int u=q.front();q.pop();
						// printf("%d\n",u);
						For(i,0,9) {
							if(!son[u][i]) son[u][i]=son[fail[u]][i];
							else fail[son[u][i]]=son[fail[u]][i],q.push(son[u][i]);
						}
					} For(i,1,idx) fs[fail[i]].push_back(i);
					// For(i,0,idx) {for(int j:{'w'-'0','x'-'0'}) printf("%d ",son[i][j]);puts("");}puts("");
					dfs(0); //For(i,0,idx) printf("%d ",dfn[i]);
					// puts("");For(i,0,idx) printf("%d ",fail[i]);puts("");
				} void mdf(int pos,int val) {for(;pos<=tot;pos+=pos&-pos) tr[pos]+=val;}
				In int qry(int pos) {int ret=0; for(;pos;pos-=pos&-pos){ret+=tr[pos];}return ret;}
				In int get(int u) {return qry(ed[u])-qry(dfn[u]-1);}
			} A1,A2;int he[N],nxt[N<<1],e[N<<1],n,m; char w[N<<1];
			namespace E {int idx=1; void adde(int a,int b,char d) {e[++idx]=b,w[idx]=d,nxt[idx]=he[a],he[a]=idx;}}
			using E::adde; struct node { int qid,val; } ; vector<node> b1[N],b2[N];
			int fa[N][23],dep[N];char from[N]; void get_fa(int u,int f) {
				dep[u]=dep[f]+1;fa[u][0]=f; For(i,1,22) fa[u][i]=fa[fa[u][i-1]][i-1];
				Grf(it,u,to) {if(to!=f) {from[to]=w[it];get_fa(to,u);}}
			} In int lca(int x,int y) { if(dep[x]<dep[y]) swap(x,y);
				Rof(i,22,0) if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
				if(x==y) return x;
				Rof(i,22,0) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
				return fa[x][0];
			} struct Que {int x,y,top,a,b,ans;} q[N];
			char S[N];int ls; In int FA(int u,int x) {Rof(i,19,0) {if(x>=(1<<i))x-=(1<<i),u=fa[u][i];}return u;}
			char ch[N],lch; In int kmp() {
				static int nxt[N];
				// printf("%s ",ch+1,S);
				nxt[1]=0; int j=0; For(i,2,ls) {
					while(j && S[j+1]!=S[i]) j=nxt[j];
					if(S[j+1]==S[i]) j++;
					nxt[i]=j;
				} int ret=0; j=0; For(i,1,lch) {
					while(j && S[j+1]!=ch[i]) j=nxt[j];
					if(S[j+1]==ch[i]) j++;
					if(j==ls) ret++,j=nxt[j];
				} return ret;
			} void dfs(int u,int ff,int r1,int r2) {
				A1.mdf(A1.dfn[r1],1);A2.mdf(A2.dfn[r2],1);
				for(auto &j:b1[u]) q[j.qid].ans+=j.val*A1.get(q[j.qid].a);
				for(auto &j:b2[u]) q[j.qid].ans+=j.val*A2.get(q[j.qid].b);
				Grf(it,u,to) if(to!=ff) dfs(to,u,A1.son[r1][w[it]-'0'],A2.son[r2][w[it]-'0']);
				A1.mdf(A1.dfn[r1],-1);A2.mdf(A2.dfn[r2],-1);
			} signed main() {
				get_fa(1,0);
				For(i,1,m) {
					int opt=read(); if(opt==1) No1=0;
					
					q[i].x=read();q[i].y=read();q[i].top=lca(q[i].x,q[i].y);
					// // printf("%d %d %d\n",q[i].x,q[i].y,q[i].top);
					 scanf("%s",S+1);ls=strlen(S+1);int u=0; 
					 // printf("%s\n",ls);
					 For(i,1,ls) {
						int &to=A1.son[u][S[i]-'0']; if(!to) to=++A1.idx;
						u=to;
					}q[i].a=u; u=0; Rof(i,ls,1) {
						int &to=A2.son[u][S[i]-'0']; if(!to) to=++A2.idx;
						u=to;
					}
					q[i].b=u; 
					if(q[i].x!=q[i].top && q[i].y!=q[i].top) {
						int b=min(ls-1,dep[q[i].x]-dep[q[i].top]);lch=b;
						for(int a=1,j=FA(q[i].x,dep[q[i].x]-dep[q[i].top]-b);j!=q[i].top;j=fa[j][0],a++) ch[a]=from[j];
						b=min(ls-1,dep[q[i].y]-dep[q[i].top]);lch+=b;
						for(int a=lch,j=FA(q[i].y,dep[q[i].y]-dep[q[i].top]-b);j!=q[i].top;j=fa[j][0],a--) ch[a]=from[j];
						q[i].ans=kmp();
					}
					if(dep[q[i].x]-dep[q[i].top]>=ls) 
						b2[q[i].x].push_back((node){i,1}),b2[FA(q[i].x,dep[q[i].x]-dep[q[i].top]-ls+1)].push_back((node){i,-1});
					if(dep[q[i].y]-dep[q[i].top]>=ls)
						b1[q[i].y].push_back((node){i,1}),b1[FA(q[i].y,dep[q[i].y]-dep[q[i].top]-ls+1)].push_back((node){i,-1});
				} A1.build(),A2.build(); dfs(1,0,0,0);
				For(i,1,m) printf("%d\n",q[i].ans);
				return 0;
			}
		} using namespace Mine;
	}
	char rd[N];
	namespace S0 {
		int ch[N],lch,S[N],ls;
		
		In int kmp() {
			static int nxt[N];
			nxt[1]=0; int j=0; For(i,2,ls) {
				while(j && S[j+1]!=S[i]) j=nxt[j];
				if(S[j+1]==S[i]) j++;
				nxt[i]=j;
			} int ret=0; j=0; For(i,1,lch) {
				while(j && S[j+1]!=ch[i]) j=nxt[j];
				if(S[j+1]==ch[i]) j++;
				if(j==ls) ret++,j=nxt[j];
			} return ret;
		}
		void solve0() {
			while(m--) {
				int opt=read(),x=read(),y=read();scanf("%s",rd+1);
				For(i,1,X) S[i]=rd[i]-'0';
				int p=lca(x,y);//printf("P: %d\n",dep[p]);
				if(opt==1) {int pos=1;
					while(x!=p) cf[x]=S[pos++],x=fa[x];
					pos=X;
					while(y!=p) cf[y]=S[pos--],y=fa[y];
				} else { lch=0;ls=X;
					while(x!=p) ch[++lch]=cf[x],x=fa[x];
					int pos=lch+dep[y]-dep[p];lch+=dep[y]-dep[p];
					// printf("POS %d\n",pos);
					while(y!=p) ch[pos--]=cf[y],y=fa[y];
					// For(i,1,lch) printf("%d ",ch[i]);
					// puts("");
					printf("%d\n",kmp());
				}
			}
		}
	} 
	signed main() {
		n=read(),m=read(),X=read();
		For(i,2,n) f[i][0]=fa[i]=read();
		For(i,1,n) {dep[i]=dep[fa[i]]+1;For(j,1,20) f[i][j]=f[f[i][j-1]][j-1];}
		scanf("%s",rd+1);
		For(i,2,n) {adde(fa[i],i,rd[i-1]-'0');}
		if(n<=250 && m<=250) S0::solve0();
		// if(0) ;
		else {
			
			For(i,2,n) sol::adde(i,fa[i],cf[i]+'0'),sol::adde(fa[i],i,cf[i]+'0');
			sol::n=n,sol::m=m;
			sol::main();
		}
		return 0;
	}
}signed main() {
	// freopen("homework.in","r",stdin);
	// freopen("homework.out","w",stdout);
	return Mine::main();
}