暂无测试数据。

题目描述：

最近，大雄拿到了一个序列，他被哆啦A梦称为 循环序列 ，因为它满足 \(a_{n + 1} = a_1, \space a_{n + 2} = a_2 , .... , a_{n + i} = a_i \space (i \ge 1)\)。

假设序列 \(a\) 是一个周期为 \(n\) 的循环序列，题目给定它的前 \(n\) 项 \(a_1,a_2, .... , a_n\)。

现在，哆啦A梦有 \(q\) 个询问，每个询问给定三个整数 \(l, r, t \space (1 \le l \le r)\)，表示从区间 \([l, \space r]\) 选取两个下标不同的元素 \(a_i\) 和 \(a_j\) \((l \le i, \space j \le r, \space i \not= j)\)，请问现在有多少种方案满足 \(a_i = a_j = a_t\)。对于每一个询问，你需要输出一个整数，表示方案数。

输入描述：

本题只包含一组测试数据

第 \(1\) 行输入两个整数 \(n\), \(q\) ，分别表示循环序列的周期和询问数 \((1 \le n \le 10^5, \space 1 \le q \le 10)\)

第 \(2\) 行输入 \(n\) 个整数 \(a_1, a_2, ... a_n\)，表示循环序列的前 \(n\) 项 \((-10^5 \le a_i \le 10^5)\)

第 \(3\) \(\sim\) \((q + 2)\) 行每行输入三个整数 \(l\)，\(r\)，\(t\)，表示一个询问 \((1 \le l \lt r \le 10^6, \space |l - r| \le \frac{114514}{6} \times \frac{\int_{0}^{+\infty} \frac{x^3e^x(e^x-1)}{(e^x+1)^3}dx }{\int_{0}^{+\infty}(\frac{sinh \space x + sin \space x}{cosh \space x - cos \space x} - \frac{x}{2}) \frac{\pi}{x^2}dx}，-10^5 \le t \le 10^5)\)

输出描述：

输出 \(q\) 行，每行包含一个整数，其中第 \(i \space (1 \le i \le q)\) 行的整数表示第 \(i\) 个询问的答案。

样例

输入

6 3
1 1 4 5 1 4
1 6 1
5 9 4
5 10 5

输出

3
1
0