You are given a sequence of length \(N\) consisting of positive integers \(a_1, a_2, \ldots, a_N\). Then \(Q\) queries follow. For the \(i\)-th query you are given three positive integers \(L_i, R_i, b_i\), and you must report how many times the value \(b_i\) appears in the subarray \([L_i, R_i]\) of \(a\).

The intended solution runs in \(O(N + Q)\) time.

Input

The first line contains two integers \(N\) and \(Q\).

The second line contains \(N\) positive integers \(a_1, a_2, \ldots, a_N\).

Each of the next \(Q\) lines contains three positive integers \(L_i, R_i, b_i\), describing one query.

Constraints

• \(1 \le N, Q \le 5 \times 10^5\)
• \(1 \le a_i, b_i \le N\)
• \(1 \le L_i \le R_i \le N\)

Output

For each query, output a single line containing the answer.

Scoring

There are two subtasks. Each subtask contains multiple test cases, and you earn the subtask's score only if you solve all of its tests.

• Subtask \(1\) (60 points): \(L_i = 1\).
• Subtask \(2\) (40 points): no additional constraints.

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