Time Limit: 30000/10000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

You are given some words {Wi}. Then our stupid AC will give you a very long string S. AC is stupid and always wants to know whether one substring from S exists in the given words {Wi} .

For example, S = "abcd", and the given words {Wi} = {"bc", "ad", "dd"}. Then Only S[2..3] = "bc" exists in the given words. (In this problem, the first element of S has the index "0".)

However, this is toooooooooooo easy for acmers ! The stupid and evil AC will now change some letters in S. So could you solve this problem now?

For example, S = "abcd", and the given words {Wi} = {"bc", "ad", "dd"}. Then Only S[2..3] = "bc" exists in the given words. (In this problem, the first element of S has the index "0".)

However, this is toooooooooooo easy for acmers ! The stupid and evil AC will now change some letters in S. So could you solve this problem now?

The first line is one integer T indicates the number of the test cases. (T <=20)

Then for every case, there is one integer n in the first line indicates the number of the given words(The size of the {Wi}) . Then n lines has one string which only has 'a'- 'z'. (1 <= n <= 10000, sigma|Wi| <= 2000000) .

Then one line has one string S, here |S| <= 100000.

Then one integer m, indicating the number of operations. (1 <= m <= 100000)

Then m lines , each line is the operation:

(1)Q L R , tell AC whether the S[L..R] exists in the given strings ;

(2)C X Y , chang S[X] to Y, here Y : 'a'-'z' .

Then for every case, there is one integer n in the first line indicates the number of the given words(The size of the {Wi}) . Then n lines has one string which only has 'a'- 'z'. (1 <= n <= 10000, sigma|Wi| <= 2000000) .

Then one line has one string S, here |S| <= 100000.

Then one integer m, indicating the number of operations. (1 <= m <= 100000)

Then m lines , each line is the operation:

(1)Q L R , tell AC whether the S[L..R] exists in the given strings ;

(2)C X Y , chang S[X] to Y, here Y : 'a'-'z' .

提交代码