题目描述

给出一个长度为 $n$ 的数列 ${ a_1 , a_2 , a_3 , ... , 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$ 行，即每次询问的答案。

样例

input

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

output

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$