[Ynoi2015]盼君勿忘

题目背景

说起来,幸福本身就是因人而异的 有些人认为只要能混口饭吃就行了 有些人只要有书读就能满足 ![](https://cdn.luogu.com.cn/upload/pic/45571.png) 有些人认为只有全力地生存才是最重要的 有些人只要得到克服某种目标的瞬间就能满足 有些人只要某个人得到幸福,自己就会跟着幸福 也有些人则令人伤透脑筋地刚好相反 ![](https://cdn.luogu.com.cn/upload/pic/45572.png) 但是,大部分人都没有自觉 他们不知道究竟什么能给自己带来幸福 但是,他们会异口同声地表示想要获得幸福 那样的人即使能察觉到幸福 也没办法变得幸福 最重要的是要敢于正视自己的内心 ![](https://cdn.luogu.com.cn/upload/pic/45573.png) 【珂朵莉已经基本上不剩什么了】 ![](https://cdn.luogu.com.cn/upload/pic/45574.png) 【心灵和身体,珂朵莉基本上快要全部失去了】 ![](https://cdn.luogu.com.cn/upload/pic/45575.png) 【全部被我替换了】 ![](https://cdn.luogu.com.cn/upload/pic/45576.png) 【幸好你在失去一切之前,回到了这里】 【喜悦和悲伤】 【还有喜欢某个人的情绪】 【现在依旧还残存着一些吧?】 嗯... 确实还有那么一丝... 【那就没问题了】 【珂朵莉你,依旧是珂朵莉】 ![](https://cdn.luogu.com.cn/upload/pic/45578.png) ![](https://cdn.luogu.com.cn/upload/pic/45579.png) 威...廉...? ![](https://cdn.luogu.com.cn/upload/pic/45580.png)

题目描述

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

输入输出格式

输入格式


第一行两个数n,m 第二行n个数表示这个序列 之后m行,每行三个数l,r,p表示查询的区间与模数

输出格式


m行,每行输出一个数表示答案

输入输出样例

输入样例 #1

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

输出样例 #1

6
6
1
6
0

说明

Idea:nzhtl1477,Solution:nzhtl1477,Code:nzhtl1477,Data:nzhtl1477 对于100%的数据,n,m,ai <= 100000,p <= 1000000000