You are given:

• An array $A$ of $n$ positive integers.
• $q$ queries of form $(l, r, x)$, count the occurences of $x$ in subarrary $A_l, A_{l + 1},…,A_r$.

Input

• The first line contains 2 integer $n, q$.
• The second line contains $n$ space-separated integers $A_i$.
• The next $q$ lines, each line contains 3 space-separated integers $l, r, k$.

Output

• Print $q$ lines, $i^{th}$ line is an integer, the answer to query $i$.

Constraints

• $1 \le n, q, k, A_i \le 10^{5}$.
• $1 \le l \le r \le n$.

Example

Input:

7 3
1 2 1 4 2 4 2
1 4 1
2 7 2
3 5 4

Output:

2
3
1