Match Me If You Can
Your friend Bela is a clever girl and she always outsmarts you some how. So this time you want to outsmart her. To do so, you have figured out a function which is almost impossible to solve, or at least it looks that way:
function IsSame(x1, y1, x2, y2) Str1 = Substring of A from x1 to y1 Str2 = Substring of A from x2 to y2 Str3 =  length1 = y1 - x1 + 1 length2 = y2 - x2 + 1 If length1 not equals length2 return false end half = floor(length1 / 2) For i = half + 1 to length1 Str3.push(Str1[i]) end For For i = 1 to half Str3.push(Str1[i]) end For For i = 1 to length1 If Str3[i] not equals Str2[i] return False end If end For return True end function Note: Array indexing starts from 1.
Now, you are gonna give her two ranges at a time and ask her to calculate if those two ranges matches each other.
The first line contains two integer N - number of characters in A and Q - number of queries. Next line contains N characters denoting the elements of string A.
Next there are Q queries with four integers which is described above. Each query will have 4 integers x1, y1, x2, y2.
- 1 ≤ N, Q ≤ 105
- 1 ≤ x1 ≤ y1 ≤ N
- 1 ≤ x2 ≤ y2 ≤ N
For each query print “Yes” if the ranges match otherwise print “No”.
6 1 abcbac 1 2 4 5