Chtholly gives you a sequence. For each query, you need to find the sum of all distinct subsequences of the subarray $[l, r]$, modulo $p$.

Input

The first line contains two integers $n$ and $m$.

The second line contains $n$ integers representing the sequence.

The following $m$ lines each contain three integers $l, r, p$, representing the query range and the modulus.

Output

Output $m$ lines, each containing a single integer representing the answer.

Examples

Input 1

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

Output 1

6
6
1
6
0

Note

Idea: nzhtl1477, Solution: nzhtl1477, Code: nzhtl1477, Data: nzhtl1477

For $100\%$ of the data, $1\leq n,m,a_i \leq 10^5$, $1\leq p\leq 10^9$, $1\leq l\leq r\leq n$.