orz 一发出题人（话说我 AC 这道题的时候，出题人好像就坐在我的右侧呢/cy/cy）
考虑一个很 naive 的 DP，(dp_i) 表示 ([l,i]) 之间的字符串是否可以被识别，转移就枚举上一段的终止为止，然后 SAM/哈希判断子串是否在 (s) 中出现过。
注意到一个事实：所有长度 (>2k) 的字符串都可以由长度 (ge k) 的字符串拼成，也就是说只有长度在 ([k,2k]) 的字符串是有用的，故每次转移只用枚举 (k+1) 个转移点。注意到 (k) 的数据范围很小，因此我们可以考虑矩阵优化转移，即对于大小分别为 (n imes m) 和 (m imes k) 的矩阵 (A,B)，定义其乘积 (C) 满足 (C_{i,j}= ext{or}_{t=1}^mA_{i,t}land B_{t,j})，那么
其中 (g_j) 表示 ([i-j+1,i]) 是否为 (s) 的子串。
显然每次修改一个区间最多改变 (r-l+1+2k) 个位置的转移矩阵，因此我们有一个很自然的想法：线段树维护矩阵乘积，每次暴力修改线段树对应的位置的值，求一个位置的转移矩阵可用 SAM。查询就求一遍区间矩阵乘积，这样复杂度大概是 ((L+qk)·k^3log n+qk^3log n)，显然无法通过，不过这里矩阵每个元素都是 0/1，因此可以用位运算加速实现 (k^2) 矩阵乘法，这样复杂度可达到 ((L+qk)·k^2log n+qk^2log n)，还是无法通过。再观察到每次修改是一段区间，因此考虑对这一段区间上的叶子节点到根节点路径的并上的节点，重新计算它们转移矩阵的乘积，这样假设待重构的区间长度为 (len)，每次重构需要进行矩阵乘法的次数大概是 (sumlimits_{n}lfloordfrac{len}{n} floor=mathcal O(len)) 级别的，这样加号前面的 (log n) 可以省去，复杂度就达到了 ((L+qk)·k^2+qk^2log n)，可以通过。
const int MAXN=3e6;
const int MAXM=3e5;
const int MAXP=6e6;
const int MAXK=16;
int n,m,k,qu;char s[MAXN+5],t[MAXM+5];
int ch[MAXP+5][9],len[MAXP+5],lnk[MAXP+5],cur=1,ncnt=1;
void extend(char c){
int id=c-'a',nw=++ncnt,p=cur;
len[nw]=len[cur]+1;cur=nw;
while(p&&!ch[p][id]) ch[p][id]=nw,p=lnk[p];
if(!p) return lnk[nw]=1,void();
int q=ch[p][id];
if(len[q]==len[p]+1) return lnk[nw]=q,void();
int cl=++ncnt;len[cl]=len[p]+1;
lnk[cl]=lnk[q];lnk[q]=lnk[nw]=cl;
for(int i=0;i<9;i++) ch[cl][i]=ch[q][i];
while(p&&ch[p][id]==q) ch[p][id]=cl,p=lnk[p];
}
struct mat{
int a[MAXK+2];
mat(){memset(a,0,sizeof(a));}
mat operator *(const mat &rhs){
mat res;
for(int i=0;i<k*2;i++) for(int j=0;j<k*2;j++)
if(a[i]>>j&1) res.a[i]|=rhs.a[j];
return res;
}
void print(){
for(int i=0;i<k+k;i++) for(int j=0;j<k+k;j++)
printf("%d%c",a[i]>>j&1,"
"[j==k+k-1]);
}
};
int lf[MAXM+5],used[MAXM*4+5];
mat calc(int l){
mat ret;
for(int i=0;i+1<k+k;i++) ret.a[i]|=1<<i+1;
int curp=1;
for(int i=1;i<=min(l,k+k);i++){
if(!ch[curp][t[l-i+1]-'a']) break;
curp=ch[curp][t[l-i+1]-'a'];
if(i>=k) ret.a[i-1]|=1;
}
// printf("calc %d
",l);
// ret.print();
return ret;
}
namespace segtree{
struct node{int l,r;mat v;} s[MAXM*4+5];
void build(int k,int l,int r){
s[k].l=l;s[k].r=r;
if(l==r){s[k].v=calc(l),lf[l]=k;return;}
int mid=l+r>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);
s[k].v=s[k<<1].v*s[k<<1|1].v;
}
void rebuild(int k){
if(!used[k]) return;used[k]=0;
if(s[k].l==s[k].r) return;
rebuild(k<<1);rebuild(k<<1|1);
s[k].v=s[k<<1].v*s[k<<1|1].v;
}
mat query(int k,int l,int r){
if(l<=s[k].l&&s[k].r<=r) return s[k].v;
int mid=s[k].l+s[k].r>>1;
if(r<=mid) return query(k<<1,l,r);
else if(l>mid) return query(k<<1|1,l,r);
else return query(k<<1,l,mid)*query(k<<1|1,mid+1,r);
}
}
void rebuild(int l,int r){
static char buf[MAXM+5];scanf("%s",buf+1);
for(int i=l;i<=r;i++) t[i]=buf[i-l+1];
for(int i=l;i<=min(r+k+k,m);i++){
for(int j=lf[i];j;j>>=1) used[j]=1;
segtree::s[lf[i]].v=calc(i);
} segtree::rebuild(1);
}
int main(){
// freopen("passage.in","r",stdin);
// freopen("passage.out","w",stdout);
scanf("%*d%s%s%d%d",s+1,t+1,&k,&qu);
n=strlen(s+1);m=strlen(t+1);
for(int i=n;i;i--) extend(s[i]);
segtree::build(1,1,m);
while(qu--){
int opt;scanf("%d",&opt);
if(opt==1){
int l,r;scanf("%d%d",&l,&r);
rebuild(l,r);
} else {
int l,r;scanf("%d%d",&l,&r);
mat v=segtree::query(1,l,r);
printf("%s
",(v.a[0]&1)?"Yes":"No");
// v.print();
}
}
return 0;
}