Counting Queries

Problem Description

Given an array $\{A\}$ of length $N$, answer $Q$ queries asking for the number of elements in the interval $[L_i, R_i]$ that are not greater than $H_i$.

There are $T$ test cases in total.

Input Format

The input is formatted as follows:

T
N Q
A1 A2 A3 ... AN
L1 R1 H1
L2 R2 H2
...
LQ RQ HQ
...

Output Format

For the $T$ test cases, output one line per case containing $Q$ space-separated integers — the answers.

Sample Input

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

Sample Output

4 0 1

Sample note: $A[3..9] = [\underline{2}, 7, \underline{5, 4, 3}, 8, 7]$, among which the number of elements not greater than $6$ is $4$.

Constraints

• $1 \le N, Q \le 10^5$
• $0 \le A_i, H \le 10^9$
• $1 \le L \le R \le N$

Data guarantee: $\sum N, Q \le 10^5$