## KDOMINO - K-dominant array

no tags

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.