Go Back

##### TML Events (100)

Description

**Problem Author: Shridhar Ravi**

TML is around the corner and GSTians are excited about it. Omkar has been chosen as the Fest Coordinator this year. He has introduced a new system of participating in the events this TML.

There are **N** different events with some entry fees. With this new system of his, students can buy an *Entry card* worth Rs. **K**. But, this card is non-rechargeable and can be used exactly for 2 events, such that the entry fees of both the events are not greater than Rs. **K**.

Omkar has listed all the events and their entry fees and has **Q** queries. He has specified a range of events, from **L** to **R** (both **L** and **R** inclusive). He needs your help to know how many different combinations of events a student can participate in the specified range for a card worth Rs. **K**.

Input

The first line of the input contains two space-separated integers **N** and **Q**, denoting the number of events and the number of queries respectively.

The next line contains **N** space-separated integers denoting the entry fees of each event.

The next **Q** lines contain 3 space-separated integers **L**, **R**, and **K** denoting the range and worth of the entry card respectively.

Output

For each query **Q**, output the integer denoting the different combinations of events possible.

Constraints

1 ≤ N ≤ 10^3

1 ≤ Q ≤ 10^3

1 ≤ L ≤ R ≤ N

1 ≤ Entry fee ≤ 10^3

1 ≤ K ≤ 2*(10^3)

Example

Copy Input

**Input**:

7 3

5 1 2 3 2 3 1

1 4 3

1 5 4

2 7 3**Output**:

1

4

5

Explanation

For the 1st query, there is only one combination possible in the given range:

2nd event (Fee: 1) + 3rd Event (Fee: 2)=3

For the 2nd query, there are 4 combinations possible in the given range:

2nd event (Fee: 1) + 3rd Event (Fee: 2)=3 (which is less than card’s worth K=4)

2nd event (Fee: 1) + 4th Event (Fee: 3)=4

2nd event (Fee: 1) + 5th Event (Fee: 2)=3 (which is less than card’s worth K=4)

3rd event (Fee: 2) + 5th Event (Fee: 2)=4