题目描述

小 Z 有一个序列 $A=\{a_1,a_2,\cdots, a_n\}$，其中 $a_i$ 都是 int 范围内的数。

现在会进行 $q$ 次询问，每次询问输入三个数 $l,r,k$ 表示询问下标在 $[l,r]$ 之间的数字中出现了多少个数字 $k$。即问 $a_l,a_{l+1},\cdots,a_r$ 中有几个 $k$。

输入格式

第一行，两个空格隔开的正整数 $n,q$ 分别表示序列长度和询问次数。

第二行,$n$ 个空格隔开的整数，第 $i$ 个整数为$a_i$，表示序列。

接下来 $q$ 行，每行三个整数 $l,r,k$ 描述一个询问。

输出格式

对于每次询问，输出一行一个整数代表答案。

样例

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

1
2
1

提示

对于 $50\%$ 的数据，$n,q \le 2000$

对于 $100\%$ 的数据，$n,q \le 100000$，$a_i$ 和 $k$ 在 int 范围内。