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.
