题目描述
给出一个长度为 $n$ 的数列 $\{a_1, a_2, a_3, \dots, a_n\}$，以及 $m$ 组询问 $(l_i, r_i, k_i)$，求区间 $[l_i, r_i]$ 中有多少数在该区间中的出现次数与 $k_i$ 互质。

输入格式
第一行，两个正整数 $n, m$。
第二行，$n$ 个正整数 $a_i$ 描述这个数列。
接下来 $m$ 行，每行三个正整数 $l_i, r_i, k_i$，描述一次询问。

输出格式
输出 $m$ 行，即每次询问的答案。

样例
输入

10 5
1 1 1 1 1 2 2 2 2 2
4 7 2
4 7 3
4 8 2
4 8 3
3 8 3

输出

0
2
1
1
0

数据范围与提示
$1\le n,m\le 5\times 10^4$ $1\le a_i\le n$ $1\le l_i\le r_i\le n$ $1\le k_i\le n$