Super Mario (Super Mario)

Source: HDU

Version: Phuoc Hung OJ Extended

Problem

There are $n$ bricks at positions $0..n-1$, with height $h_i$. For each query $L,R,H$, count positions in $[L,R]$ whose height is at most $H$.

Input

The first line contains $n,m$, the second line contains the heights, and each next line contains $L,R,H$.

Output

Print the number of bricks with height at most $H$ for every query.

Subtasks

Subtask 1 (20%)

• $n\le 30$, number of queries $\le 30$.
• All other conditions are the same as Subtask 3.

Subtask 2 (30%)

• $n\le 3000$, number of queries $\le 3000$.
• All other conditions are the same as Subtask 3.

Subtask 3 (50%)

• $1\le n,m\le10^5$
• $0\le h_i,H\le10^9$
• $0\le L\le R<n$
• indexing is 0-based

Example

Input

10 10
0 5 2 7 5 4 3 8 7 7
2 8 6
3 5 0
1 3 1
1 9 4
0 1 0
3 5 5
5 5 1
4 6 3
1 5 7
5 7 3

Output

4
0
0
3
1
2
0
1
5
1

Explanation

For the first query, the heights at positions $2..8$ are [2,7,5,4,3,8,7]; four are at most $6$.