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

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 **i ^{th}** area is

**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 ≤ 10 ^{5})**.

The next line will contain **n** integers denoting **affect _{1}, affect_{2}, …, affect_{n} (1 ≤ affect_{i} ≤ 10^{9})**.

The next **m** lines will be followed by four integer **L**, **R**, **P** and **Q (1 ≤ L ≤ R ≤ n, 1 ≤ P ≤ Q ≤ 10 ^{9})**.

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

Input | Output |
---|---|

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 In the second query, there is no affect value between |

39% Solution Ratio

prodip_bsmrstuEarliest,

prodip_bsmrstuFastest, 0.2s

sakibalaminLightest, 26 MB

AdnanAlMaruf_9Shortest, 1594B

Login to submit