## Description

As you know, the world is suffering from Covid-19. Teams of scientists are currently working

on developing vaccines for this deadly disease.

Chandu being a medical sciences student, is currently working on studying the history of

corona viruses. He found out that viruses evolve. Each virus has a DNA sequence (which

can be represented by a sequence of uppercase characters). Whenever a virus evolves,

some of the DNAs in the sequence gets modified.

Chandu found out that corona viruses have a particular DNA sequence X, of length N.

Chandu is working on a medicine V of length M (medicine is also represented as a sequence

of uppercase characters). The medicine V can be used to cure covid-19 only if the DNA

sequence X of the virus contains within it the DNA sequence of the medicine and the number

of such occurrences (C1) is atleast K i.e. medicine V will cure the disease X if V is a substring

of X and number of occurrences of V in X is greater than equal to K.

Also the virus X has evolved and a new virus Y has been generated. The evolution happens

in the following way –

X(1…N) is the old DNA sequence. Evolution happens in Q stages. In the i

th

stage, each

character of the substring X(L…R) gets rotated by s characters (1<=L,R<=N). Rotation of a i
character c by s means shifting c by characters towards right in the alphabet sequence i
s
i
(which involves looping back from ‘Z’ to ‘A’ if needed)
For Example -
1) Rotating ‘A’ by 1 gives ‘B’.
2) Rotating ‘D’ by 5 gives ‘I’.
3) Rotating ‘Y’ by 4 gives ‘C’.
4) Rotating ‘A’ by 30 gives ‘E’ and so on.
X undergoes Q such evolutions and we obtain Y. Now chandu wants to find if the same
medicine V will work on the new virus Y i.e. if number of occurrences of V in Y (C2) is atleast
K.
Chandu finds this task difficult. Since Chandu is your friend, you need to help him find the
string Y and whether the medicine will cure X and Y.
Input Format
First line of input contains the number of test cases T.
For each test case, the first line contains the DNA sequence of the initial virus (X).
Next line contains the DNA sequence of the medicine (V).
Next line contains a single integer K.
Next line contains a single integer Q, the number of evolutions to be performed on X.
Each of the next Q lines contains three integers L , and , such that each character of
i Ri
si
X( L ... R ) gets rotated by characters(1<=i<=Q)
i i
si
Output Format
For each test case, output will contain three lines.
First line contains a string YES if medicine V can cure the disease X and NO if the disease can not be
cured.
Next line contains the count of occurrences of V in X (C1).
Next line contains the DNA sequence Y.
Next line contains a string YES if medicine V can cure the disease Y and NO if the disease can not be
cured.
Next line contains the count of occurrences of V in Y (C2).
Constraints
1 <= T <= 10
1 <= N <= 10^5 (N is the length of string X)
1 <= M <= 10^5 (M is the length of string V)
1 <= Q <= 10^5
1 <= K <= 10^5
Sample Test case
Input 1 -
1
ABBBCBBBBD
BBB
2
2
1 1 4
8 10 1
Output 1 -
YES
3
EBBBCBBCCE
NO
1
Explanation -
String\Index 1 2 3 4 5 6 7 8 9 10
X A B B B C B B B B D
After First
Modification
E B B B C B B B B D
After Second
modification(Y)
E B B B C B B C C E
X has three occurrences of substring V i.e. X(2..4), X(6..8) and X(7..9) matches V.
Since 3>=2, the answer is YES.

Y has only one occurrence of substring V and hence the answer is NO.

Note – Two substrings are considered different if they have at least one non common

index. Also substring X(L..R) includes both L and R also.