P7770 "CGOI-1" Ugly Country Tourism.

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

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

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 $m$ lines. The $i$-th line is the $i$-th person's total comfort value modulo $10^9+7$.

#### 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.** | ID | Special Constraints | Score | Time Limit | | :-: | :-: | :-: | :-: | | Subtask0 | $n,\,m\le 10^4$ | 20pts | 1s | | Subtask1 | $a_i,\,x\le 10$ | 10pts | 2s | | Subtask2 | $a_i$ is strictly increasing | 10pts | 2s | | Subtask3 | No special constraints | 60pts | 2s | 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