Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Dengue Affected Areas

By emrul_mu · Limits 2s, 256 MB

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.

Input

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).

Output

For each query, output three integers as defined in the problem statement.

Sample

InputOutput
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.



Discussion
Statistics
Submit

Login to submit