Background

Ugly Country has beautiful scenery and is a well-known tourist destination (not really). Many people come to travel in Ugly Country.

Problem Description

In one part of Ugly Country, there are $n$ cities numbered from $1$ to $n$. When a person is in city $i$, they can and can only go to city $i+1$.

People in city $i$ hate people whose ugliness value is $a_i$ the most. When a person with ugliness value $x$ walks from city $i$ to city $i+1$, they gain a comfort value of $|x-a_i|\times|x-a_{i+1}|$.

Now there are $m$ people coming to travel in Ugly Country. The $i$-th person has ugliness value $x_i$ and will walk from city $l_i$ to city $r_i$. Ask for the sum of the comfort values they obtain.

Since this number may be very large, you need to output it modulo $10^9+7$.

Since you cannot predict the next trip, the queries will be forced to be online.

Simplified statement:

Given $n$ and $n$ integers $a_1,\,a_2,\,\dots,\,a_n$.

There are $m$ online queries. Each query gives $x,\,l,\,r$. Compute $\sum\limits_{i=l}^{r-1}|x-a_i|\times|x-a_{i+1}|$.

Input Format

The first line contains two integers $n,m$, representing the number of cities and the number of tourists.

The second line contains $n$ integers. The $i$-th number is $a_i$, with the meaning as described above.

In the next $m$ lines, each line contains three integers $X,\,L,\,R$. Let $s$ be the total comfort value of the previous query modulo $10^9+7$ (if this is the first query, then $s=0$). Then $x_i=X\operatorname{xor}s,\;l_i=L\operatorname{xor}s,\;r_i=R\operatorname{xor}s$, where $\operatorname{xor}$ denotes bitwise XOR, and the meanings of $x_i,\,l_i,\,r_i$ are as described above.

Output Format

Output $m$ lines. The $i$-th line is the $i$-th person's total comfort value modulo $10^9+7$.

5 2
1 2 3 4 5
1 1 3
6 1 7

2
0

Hint

Sample Explanation:

For the first query, walking from city $1$ to city $2$ gives a comfort value of $|1-1|\times|1-2|=0$. Walking from city $2$ to city $3$ gives a comfort value of $|1-2|\times|1-3|=2$. Therefore, the total comfort value is $2$.

For the second query, the decrypted $x,\,l,\,r$ are $4,3,5$. Walking from city $3$ to city $4$ gives a comfort value of $|4-3|\times|4-4|=0$. Walking from city $4$ to city $5$ gives a comfort value of $|4-4|\times|4-5|=0$. The total comfort value is $0$.

Constraints:

This problem uses bundled testdata.

For $100\%$ of the testdata, $1 \le n,\,m \le 3 \times 10^5$, $1 \le a_i,\,x_i \le 10^9$, $1 \le l_i < r_i \le n$.

Translated by ChatGPT 5