Frequency Query

You are given a positive integer sequence $A$ of length $n$.

There are $q$ queries. In the $i$-th query ($1 \le i \le q$), you are given three integers $l_i$, $r_i$, and $x_i$. You need to determine the number of times $x_i$ appears in the subarray $A_{l_i}, A_{l_i+1}, \dots, A_{r_i}$.

inputFormat

The first line contains two integers $n$ and $q$.

The second line contains $n$ positive integers representing the sequence $A$.

Each of the following $q$ lines contains three integers $l_i$, $r_i$, $x_i$ describing a query.

outputFormat

For each query, output one integer — the number of occurrences of $x_i$ in the subarray $A_{l_i}, A_{l_i+1}, \dots, A_{r_i}$.

sample

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

3
1
1