Vikas0706 is an awesome bar tender. He has never failed is satisfying his customers. One fine evening, after getting frustrated and tired a programmer came to his bar. He thought to remove all his frustration on Vikas0706.
There are N different types of drink kept in a line on the table. Every drink can be of different quantity (in ml) . Now programmer asked Vikas0706 to make a cocktail of quantity k ml using only 2 drinks. Also he has to completely consume the drink he selects. Vikas0706 is really confused which two drink to select. Now programmer didn't stop here. He further told him to select drinks only from a range l to r (both l and r inclusive) . Vikas0706 is in a big trouble now. You are his last hope. Tell him how many different type of cocktails he can make in the specified range satisfying the conditions of the programmer.
INPUT FORMAT
First line contains two integers N and Q denoting the number of drinks and number of queries.
Second line contains N integers denoting the quantity of the drinks in ml.
Next Q lines contains 3 integer l,r and k denoting the range and the quantity of the cocktail the programmer wants.
INPUT FORMAT
For each query Q output the integer denoting number of different types of cocktails Vikas0706 can make .
CONSTRAINTS
1 ≤ N ≤ 106
1 ≤ Q ≤ 104
1 ≤ l ≤ r ≤ N
1 ≤ Quantity of drinks in ml ≤ 103
1 ≤ K ≤ 2*103
For query 1:
2nd drink(1) + 3rd drink(2) =3
There is only one combination for making a cocktail of 3 ml.
For query 2:
2nd drink(1) + 4th drink(3) =4
3rd drink(2) + 5th drink(2) =4
There is only two combination for making a cocktail of 4 ml.
For query 3:
2nd drink(1) + 3rd drink(2) =3
2nd drink(1) +5th drink(2) =3
3rd drink(2) + 7th drink(1) =3
5th drink(1) + 7th drink(1) =3
There is only four combination for making a cocktail of 3 ml.
