KDOMINO  Kdominant array
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 Kdominant notation. An array with length L is called Kdominant, 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 kdominant 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 32bit 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.
hide comments
swapnil_007:
20171009 06:47:09
Last edit: 20171010 21:55:44 

julkas:
20171008 14:34:23
@swapnil_007. My offline solution passed. And FREQ2. Try first FREQ2. Last edit: 20171008 14:39:17 

swapnil_007:
20171008 11:35:54
Will O(N*sqrt(N)*log(N)) pass? 

wisfaq:
20171004 20:13:43
Last edit: 20171004 20:14:04 

Min_25:
20171002 18:37:37
@Blue.Mary: Yes.


[Rampage] Blue.Mary:
20171002 17:30:20
Does 1 <= l <= r <= N hold for all test cases?

Added by:  mahmud2690 
Date:  20171002 
Time limit:  2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  Me, MYSELF & I 