Dengue Affected Areas
Dengue, the talk of the town of Dhaka this year. So many people suffered from dengue fever and a number of people died. In this problem, you are going to process some queries with some given information about the affects of dengue.
There are n most dengue affected areas in Bangladesh. These are numbered from 1 to n. The affect value of the ith area is affecti. Now, you need to process m queries. A query is defined as,
L R P Q: You need to print,
- Count of areas numbered from L to R where dengue affect is at least P and at most Q.
- Minimum affect value which is present in area L to R and between P to Q. If there is no such value, print -1.
- Maximum affect value which is present in area L to R and between P to Q. If there is no such value, print -1.
The first line of input will contain two integers n and m (1 ≤ n, m ≤ 105).
The next line will contain n integers denoting affect1, affect2, …, affectn (1 ≤ affecti ≤ 109).
The next m lines will be followed by four integer L, R, P and Q (1 ≤ L ≤ R ≤ n, 1 ≤ P ≤ Q ≤ 109).
For each query, output three integers as defined in the problem statement.
3 2 1 2 3 1 3 1 3 1 3 4 5
3 1 3 0 -1 -1
In the first query, there are three affect values [1, 2, 3] between P = 1 and Q = 3 in area L = 1 to R = 3. So the first integer of the output is 3. Among these, the minimum is 1 and the maximum is 3, so the next two integers of the output is 1 and 2 respectively.
In the second query, there is no affect value between P = 4 and Q = 5 in area L = 1 to R = 3.