Description

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$.

Input Format

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 Format

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

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.

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