这是一次不寻常的比赛中的一个不寻常的问题,这里是公告:http://codeforces.com/blog/entry/73543
你经营一家琴弦店。在一天中,您的客户想要购买一定长度的字符串,有时还需要满足其他属性。
您有一个长度为 $$$n$$$ 的字符串,并且可以从其中的任意位置开始剪切任意长度的字符串。今天,您的第一位客户问您一些类型的问题“如果长度为 $$$k$$$ 的子字符串中的一个从位置 $$$i$$$ 开始,而另一个从第 $$$j$$$ 个位置开始,那么它们之间有什么区别吗?”你要回答所有这些问题。
请注意,在您的商店中,字符串超过了 $$$987\,898\,789$$$ 大小的字母表。
输入
第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1\leq q, n\leq 200\,000$$$)。第二行包含 $$$n$$$ 空格分隔的整数 $$$a_1$$$, ..., $$$a_n$$$ ($$$0\leq a_i < 987\,898\,789$$$) 表示字符串 $$$s$$$ 的字母,接下来的 $$$q$$$ 行包含三个整数 $$$len$$$, $$$pos_1$$$ 和 $$$pos_2$$$ ($$$1\leq len\leq n$$$, $$$1\leq pos_1, pos_2\leq n - len + 1$$$) 表示相应的查询。
输出
打印 $$$q$$$ 行,如果第 $$$i$$$ 查询中的两个子字符串(从 $$$pos_1$$$ 和 $$$pos_2$$$ 开始的长度 $$$len$$$ 相等,则打印第 $$$i$$$ 行,其中包含 Yes,否则包含 No。
示例
输入 #1
5 2 1 2 3 1 2 2 1 4 3 1 3
输出 #1
Yes No
输入 #2
9 3 0 0 0 0 0 0 0 0 0 9 1 1 8 1 2 1 1 9
输出 #2
Yes Yes Yes