Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Match Me If You Can

Limits 1s, 512 MB

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.

Input

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

Output

For each query print “Yes” if the ranges match otherwise print “No”.

Samples

InputOutput
6 1
abcbac
1 2 4 5
Yes

Discussion