Description

珂朵莉给了你一个序列，每次查询一个区间 $[l,r]$ 中所有子序列分别去重后的和 $\bmod\ p$。

Input Format

第一行两个整数 $n,m$。

第二行 $n$ 个整数表示这个序列。

之后 $m$ 行，每行三个整数 $l,r,p$ 表示查询的区间与模数。

Output Format

$m$ 行，每行输出一个整数表示答案。

5 5
1 2 2 3 4
1 2 233333
2 3 333333
1 5 5
3 5 15
2 4 8

6
6
1
6
0

Hint

Idea：nzhtl1477，Solution：nzhtl1477，Code：nzhtl1477，Data：nzhtl1477

对于 $100\%$ 的数据，$1\leq n,m,a_i \leq 10^5$，$1\leq p\leq 10^9$，$1\leq l\leq r\leq n$。