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
```