String and String

Problem Description

You are given two strings S and T ,we define the "Sval" :

1. consider the substring $T.substring(a_i\otimes ans,b_i\otimes ans)$ in the substring $S.substring(c_i\otimes ans,d_i\otimes ans)$ perfect matching.
2. assume all the positions of matching is $[x_0,y_0],[x_1,y_1]...[x_k,y_k]$ while $T.substring(a_i\otimes ans,b_i\otimes ans)$=$S.substring(x_0,y_0)$=$S.substring(x_1,y_1)$=...=$S.substring(x_k,y_k)$ $\quad (c_i\otimes ans\leq x_i,y_i\leq d_i\otimes ans)$
3. define then $Sval=\sum_{i=0}^{k}f[y_i]$ And Zhu thinks it's too easy and he can modify the $f[a_i\otimes ans]$ to $b_i\otimes ans$. note:
4. the "$ans$" shows before is the answer of the last query,at first ans=0.
5. the symbol "$\otimes$" is xor in binary system
6. the index is 0-based

Input

The first line is an integer T($1 \leq T \leq 10$) describe the number of test cases. Each test case begins with two strings S and T,($|S|,|T|\leq 100000,\sum{|S|+|T|}\leq 400000$,each character is lowercase letters from the alphabet). Then a line contains $|S|$ numbers describe each element of $f$.($0 \leq f_i \leq 10000$) The next line contains number of operators Q ($Q\leq 100000,\sum{Q}\leq 200000$). The operators have two types: 1.modify the $f[a_i\otimes ans]$ to $b_i\otimes ans$ ($0\leq b_i\otimes ans\leq 10000$) 2.query the Sval of $T.substring(a_i\otimes ans,b_i\otimes ans)$ in $S.substring(c_i\otimes ans,d_i\otimes ans)$ The remaining Q lines contain operators in the form $t_i\ a_i\ b_i$ if $t_i=1$;$t_i\ a_i\ b_i\ c_i\ d_i$ if $t_i=2$ denoting the type of the operators and the parameters respectively.

Output

For each query output one integer which means the answer.

Sample Input

1

aaaa

aaaa

0 1 2 3

3

2 0 0 0 3

1 6 3

2 6 6 6 5

Sample Output

6

11

Source

2017 Multi-University Training Contest - Team 2

https://acm.hdu.edu.cn/showproblem.php?pid=6054