P5072 [Ynoi Easy Round 2015] Please Do Not Forget

Generally speaking, happiness itself differs from person to person. Some people think it is enough as long as they can get something to eat. Some people are satisfied as long as they can read books.  Some people think that surviving with all their strength is the most important thing. Some people are satisfied the moment they overcome some goal. Some people feel happy as long as someone else becomes happy, and they become happy along with them. And there are also people who are, to make you rack your brain, exactly the opposite.  However, most people are not aware of themselves. They do not know what exactly can bring them happiness. But they will say in unison that they want to obtain happiness. Even if such people can notice happiness, they still cannot become happy. The most important thing is to dare to face your own heart directly.  【Chtholly basically has almost nothing left】  【In mind and body, Chtholly has basically almost lost everything】  【I replaced all of it】  【Luckily, before you lost everything, you came back here】 【Joy and sorrow】 【And the feeling of liking someone】 【There are still some of them left now, right?】 Mm... There is indeed just a little bit left... 【Then there is no problem】 【Chtholly, you are still Chtholly】   Wi... llem...? 

Chtholly gives you a sequence. For each query, compute the sum of all subsequences in the interval $[l,r]$ after removing duplicates within each subsequence, and output the result $\bmod\ p$.

The first line contains two integers $n,m$. The second line contains $n$ integers representing the sequence. Then follow $m$ lines, each containing three integers $l,r,p$, describing the queried interval and the modulus.

Output $m$ lines. Each line contains one integer, the answer.

Idea: nzhtl1477, Solution: nzhtl1477, Code: nzhtl1477, Data: nzhtl1477. Constraints: For $100\%$ of the testdata, $1\leq n,m,a_i \leq 10^5$, $1\leq p\leq 10^9$, $1\leq l\leq r\leq n$. Translated by ChatGPT 5