You are given a sequence \(a_1, a_2, \ldots, a_N\) of length \(N\) and \(Q\) queries. Each query has three parameters \(L, R, x\); for that query, report how many values equal to \(x\) appear among the \(R - L + 1\) elements from \(a_L\) through \(a_R\).

Input

The first line contains two integers \(N\) and \(Q\) (\(1 \le N, Q \le 5 \times 10^5\)).

The second line contains \(N\) integers \(a_1, a_2, \ldots, a_N\) (\(1 \le a_i \le 5 \times 10^5\)).

Each of the next \(Q\) lines contains three integers \(L\), \(R\), and \(x\), describing a query.

Output

For each query, output a line with a single integer representing the answer.

Sample Input 1

5 6
1 2 3 1 1
1 5 1
1 3 1
2 4 3
3 5 1
1 5 4
1 5 3

Sample Output 1

3
1
1
2
0
1