Increase 2 consecutive characters solution codechef – Chef has 22 strings AA and BB of equal length NN. Both strings contain lowercase english alphabets only. Chef can perform several moves on string AA. In one move, Chef has to: Select an index i (1≤i≤N−1)i (1≤i≤N−1). Replace A[i]A[i] with (A[i]+1)(A[i]+1). Replace A[i+1]A[i+1] with (A[i+1]+1)(A[i+1]+1).

Increase 2 consecutive characters solution codechef

Chef has 22 strings AA and BB of equal length NN. Both strings contain lowercase english alphabets only.

Chef can perform several moves on string AA. In one move, Chef has to:

  • Select an index i (1iN1)i (1≤i≤N−1).
  • Replace A[i]A[i] with (A[i]+1)(A[i]+1).
  • Replace A[i+1]A[i+1] with (A[i+1]+1)(A[i+1]+1).

For example, if A=abczeA=abcze, a valid move would be to select index 33. This way the string becomes abdaeabdae after performing the move. Note that the value at an index is cyclically incremented. This means that, aba→bbcb→czaz→a.

Chef has been asked to answer QQ queries. Each query is of the form:

  • LL RR: Given 1LRN1≤L≤R≤N, Chef wants to know if it is possible to convert the substring A[L,R]A[L,R] to B[L,R]B[L,R] by performing the above mentioned move any number of times.

For each query, output in a single line YesYes, if the conversion is possible using any number of moves. Otherwise, print NoNo.

NOTE: Queries are independent. Thus, the original strings AA and BB would be retained to process next query.

Input Format

  • The first line will contain TT – the number of test cases. Then the test cases follow.
  • First line of each test case contains two integers N,QN,Q.
  • Second line of each test case contains string AA.
  • Third line of each test case contains string BB.
  • QQ lines follow, where the ithith line contains two integers LiRiLiRi – the ithith query.

Output Format Increase 2 consecutive characters solution codechef

Output QQ lines, where the ithith line contains the answer to the ithith query. The answer is YesYes, if the conversion is possible using any number of moves. Otherwise, the answer is NoNo.

You may print each character of the string in uppercase or lowercase (for example, the strings yEsyEsyesyesYesYes and YESYES will all be treated as identical).

Constraints

  • 1T10001≤T≤1000
  • 2N1052≤N≤105
  • 1Q21051≤Q≤2⋅105
  • 1LRN1≤L≤R≤N
  • Sum of NN over all test cases does not exceed 21052⋅105.
  • Sum of QQ over all test cases does not exceed 21052⋅105.

Sample Input 1  Increase 2 consecutive characters solution codechef

1
5 3
abcdz
nbhea
2 2
1 3
4 5

Sample Output 1 

Yes
No
Yes

Explanation Increase 2 consecutive characters solution codechef

Test Case 11:

  • For the first query, the substring A[2,2]=bA[2,2]=b is already same as B[2,2]=bB[2,2]=b. Thus, the answer is YesYes.
  • For the second query, it can be proven that the substring A[1,3]A[1,3] can never be made equal to B[1,3]B[1,3] using any number of moves.
  • For the third query, the substring A[4,5]=dzA[4,5]=dz and B[4,5]=eaB[4,5]=ea. Applying the move on index 44, we get A[4]=eA[4]=e and A[5]=aA[5]=a. Hence, after one move, A[4,5]=B[4,5]A[4,5]=B[4,5]. Thus, the answer is YesYes in this case.

For Solution

Click Here

Leave a Comment