Problem Description

You are given two strings s1[0..l1], s2[0..l2] and Q - number of queries.

Your task is to answer next queries:

  1) 1 a i c - you should set i-th character in a-th string to c;

  2) 2 i - you should output the greatest j such that for all k (i<=k and k<i+j) s1[k] equals s2[k].

 

Input

The first line contains T - number of test cases (T<=25).

Next T blocks contain each test.

The first line of test contains s1.

The second line of test contains s2.

The third line of test contains Q.

Next Q lines of test contain each query:

  1) 1 a i c (a is 1 or 2, 0<=i, i<length of a-th string, 'a'<=c, c<='z')

  2) 2 i (0<=i, i<l1, i<l2)

All characters in strings are from 'a'..'z' (lowercase latin letters).

Q <= 100000.

l1, l2 <= 1000000.

 

Output

For each test output "Case t:" in a single line, where t is number of test (numbered from 1 to T).

Then for each query "2 i" output in single line one integer j.

 

Sample Input

 

Sample Output

这题属于区间合并，维护线段的llen（线段从左端点开始向右的最长连续1的长度），rlen（线段从右端点开始向左的最长连续1的长度），tlen（线段中最长连续1的长度，记录这个主要是为了剪枝，减少时间）。一开始先初始化，两个字符串，相同的部分记为1，不同的记为0，注意两个字符串的长度可能不同。

#include<iostream>

#include<stdio.h>

#include<string.h>

#include<math.h>

#include<vector>

#include<map>

#include<queue>

#include<stack>

#include<string>

#include<algorithm>

using namespace std;

#define maxn 1000100

char s1[maxn],s2[maxn];

int a[maxn],num;

struct node{

    int l,r,llen,rlen,tlen;

}b[4*maxn];

void pushup(int i)

{

    b[i].tlen=max(b[i*2].tlen,b[i*2+1].tlen);

    b[i].tlen=max(b[i].tlen,b[i*2].rlen+b[i*2+1].llen);

    b[i].llen=b[i*2].llen;b[i].rlen=b[i*2+1].rlen;

    if(b[i*2].llen==b[i*2].r-b[i*2].l+1)b[i].llen+=b[i*2+1].llen;

    if(b[i*2+1].rlen==b[i*2+1].r-b[i*2+1].l+1)b[i].rlen+=b[i*2].rlen;

}

void build(int l,int r,int i)

{

    int mid;

    b[i].l=l;b[i].r=r;

    if(l==r){

        b[i].tlen=b[i].llen=b[i].rlen=a[l];return;

    }

    mid=(l+r)/2;

    build(l,mid,i*2);

    build(mid+1,r,i*2+1);

    pushup(i);

}

void update(int id,int value,int i)

{

    int mid;

    if(b[i].l==b[i].r){

        b[i].tlen=b[i].llen=b[i].rlen=value;return;

    }

    mid=(b[i].l+b[i].r)/2;

    if(mid>=id)update(id,value,i*2);

    else update(id,value,i*2+1);

    pushup(i);

}

void question(int id,int i)

{

    int mid;

    if(b[i].l==b[i].r){

        num=1;return;

    }

    if(b[i].tlen==b[i].r-b[i].l+1){

        num=b[i].r-id+1;return;

    }

    mid=(b[i].l+b[i].r)/2;

    if(mid>=id){                //用4个剪枝试一试

        if(b[i*2].r-b[i*2].rlen+1<=id){

            num=b[i*2].r-id+1+b[i*2+1].llen;return;

        }

        else{

            question(id,i*2);

        }

    }

    else{

        if(b[i*2+1].l+b[i*2+1].llen-1>=id){

            num=b[i*2+1].l+b[i*2+1].llen-1-id+1;return;

        }

        else question(id,i*2+1);

    }

}

int main()

{

    int n,m,i,j,T,len1,len2,len,d,e,flag,c,num1=0;

    char f[10];

    scanf("%d",&T);

    while(T--)

    {

        num1++;

        printf("Case %d:\n",num1);

        scanf("%s%s",s1+1,s2+1);

        len1=strlen(s1+1);len2=strlen(s2+1);

        len=min(len1,len2);

        for(i=1;i<=len;i++){

            if(s1[i]==s2[i])a[i]=1;

            else a[i]=0;

        }

        build(1,len,1);

        scanf("%d",&m);

        for(i=1;i<=m;i++){

            scanf("%d",&c);

            if(c==1){

                scanf("%d%d%s",&d,&e,f);

                e++;

                if(e>len)continue;

                if(s1[e]==s2[e])flag=1;

                else flag=0;

                if(d==1)s1[e]=f[0];

                else s2[e]=f[0];

                if(s1[e]==s2[e] && flag==0)update(e,1,1);

                else if(s1[e]!=s2[e] && flag==1)update(e,0,1); //这里可以节省200ms

            }

            else if(c==2){

                scanf("%d",&d);

                d++;

                if(d>len || s1[d]!=s2[d]){

                    printf("0\n");continue;

                }

                num=0;

                question(d,1);

                printf("%d\n",num);

            }

        }

    }

}