题目描述

给定一个长度为 $n$ 的正整数序列 $a$。

共有 $Q$ 次询问。每次询问给出三个整数 $l,r,k$，你需要求出集合

$$\left\{ x\ \middle|\ \exists i\in[l,r],\ \left\lfloor\frac{a_i}{k}\right\rfloor=x, \ x>0 \right\}$$

中不同整数的个数。

输入格式

第一行输入两个正整数 $n,Q$，分别表示序列长度和询问次数。

第二行输入 $n$ 个正整数 $a_1,a_2,\ldots,a_n$。

接下来 $Q$ 行，每行输入三个正整数 $l,r,k$，表示一次询问。

输出格式

对每次询问输出一行一个整数，表示对应集合中不同正整数的数量。

样例

10 10
2 4 9 3 5 3 1 6 3 9
1 4 4
3 9 9
4 8 2
1 3 3
4 5 10
8 9 10
3 10 5
3 10 4
3 5 6
2 6 2

2
1
3
2
0
0
1
2
1
3

数据范围

对于所有测试数据：

• $1\le n,Q\le 2\times 10^5$；
• $1\le a_i\le n$；
• $1\le l\le r\le n$；
• $1\le k\le n$。

原题各测试点规模如下：

测试点编号	$n,Q\le$
$1\sim2$	$2\times10^3$
$3\sim4$	$10^4$
$5\sim8$	$10^5$
$9\sim20$	$2\times10^5$