4213. [Ynoi Easy Round 2015] 盼君勿忘

【题目背景】

【题目描述】

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

【输入格式】

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

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

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

【输出格式】

$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

【样例说明】

无。

【数据规模与约定】

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

由于本题找不到原数据，所以测试点来源如下。

测试点 $1\sim 3$ 随机生成。

测试点 $4\sim 5$ 从另一道 Ynoi 抠出来的。

测试点 $6\sim 7$ 卡了不看题的小朋友。

测试点 $8\sim 9$ 卡了复杂度更劣的解法。

测试点 $10$ 是某平台讨论区神秘 Hack。

数据强度可能仍然不够，如果有错解通过可以联系管理加强数据。

【来源】

Ynoi Easy Round 2015。