Professor Mahammad was sitting in his garden when an apple fell on his head, and in a stroke of brilliant insight, he suddenly came up with K-dominant notation. An array with length L is called K-dominant, if and only if there is at least one element x lying in the array for which occurence(x) * K >= L. After analyzing several arrays with this property, professor now, made up a new problem for you. Your task is simple, there are given an array of length N and several queries. For each of the queries, you just need to check whether the subarray [l, r] is k-dominant or not.

Input

The first line of the input contains two positive integers N and Q, the number of elements of the array and the mean, respectively. (N, Q ≤ 200000).

The following line contains N integers which represent elements of the array.

The following Q lines contains three integers l, r, and k. (1 ≤ l ≤ r ≤ N).

All the numbers in the input section are 32-bit positive integers.

Sum of all k's in queries does not exceed 500000.

Output

For each of the queries, print per line YES or NO if there is an element lying in the subarray which satisfies the condition in the statement.

Example

Input:
8 3
1 4 2 3 2 2 5 3
2 6 2
1 8 2
1 8 3

Output:
YES
NO
YES

Note: For the first and third queries x = 2 satisfies the condition. And for the second query there is no element for which the condition holds true.