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

1 aaabba aabbaa 7 2 0 2 1 2 2 2 3 1 1 2 b 2 0 2 3

 

Sample Output

Case 1: 2 1 0 1 4 1

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

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include