Roger has a strange array consisting of ~N~ elements, each of which is either ~1~ or ~2~. He also has ~Q~ queries, each of the form ~l~ ~r~ ~x~ which means that Roger wants to know whether there exists a subarray ~[a,b]~ where ~l \le a \le b \le r~ whose sum of elements is exactly ~x~.
In all subtasks
~1 \le N, Q \le 1\,000\,000~
~1 \le l \le r \le N~
~1 \le x \le 2N~
Each element of the array is either ~1~ or ~2~.
Subtask 1 [20%]
~1 \le N, Q \le 2\,000~
Subtask 2 [80%]
No additional constraints.
On the first line, there are two space-separated integers, ~N~ and ~Q~, denoting the number of elements in the array and the number of queries.
On the second line, there are ~N~ space-separated integers, the elements of the array.
On the next ~Q~ lines, there are three space-separated integers, ~l~ ~r~ ~x~, denoting a query.
Output ~Q~ lines, where the ~i~-th line is
YES if there exists a subarray satisfying the conditions of Roger's ~i~-th query, or
7 3 1 2 2 1 1 2 1 2 4 3 1 7 8 2 5 7
YES YES NO