307110: CF1302H. Who needs suffix structures?

This is an unusual problem in an unusual contest, here is the announcement: http://codeforces.com/blog/entry/73543

You run a string shop. During a day your customers want to buy strings of certain lengths and sometimes satisfying other properties.

You have a string of length $n$ and can cut a string of any length starting at any position out of it. Today your first customer asks you some questions of type "Is there any difference between substrings of length $k$ if one of them starts at position $i$ and another one starts from the $j$-th position?" You are to answer all these questions.

Please note that in your shop strings are over an alphabet of size $987\,898\,789$.

The first line contains two integers $n$ and $q$ ($1\leq q, n\leq 200\,000$). The second line contains $n$ space-separated integers $a_1$, ..., $a_n$ ($0\leq a_i < 987\,898\,789$) which denote the letters of string $s$, and each of the following $q$ lines contains three integers $len$, $pos_1$ and $pos_2$ ($1\leq len\leq n$, $1\leq pos_1, pos_2\leq n - len + 1$) denoting the corresponding query.

Print $q$ lines, $i$-th of them containing Yes if the two substrings in the $i$-th query (of length $len$ starting from $pos_1$ and $pos_2$) are equal and No otherwise.

5 2
1 2 3 1 2
2 1 4
3 1 3

Yes
No

9 3
0 0 0 0 0 0 0 0 0
9 1 1
8 1 2
1 1 9

Yes
Yes
Yes