P7770 「CGOI-1」丑国旅游

丑国风景优美，是远近闻名的旅游胜地（并不）。来丑国旅游的人很多。

丑国的一角排列着编号从 $1$ 到 $n$ 的 $n$ 个城市。当一个人在第 $i$ 个城市时，能且仅能走到第 $i+1$ 个城市。 第 $i$ 个城市中的人们最讨厌丑值为 $a_i$ 的人。当一个丑值为 $x$ 的人从第 $i$ 个城市走到第 $i+1$ 个城市时，他会获得 $|x-a_i|\times|x-a_{i+1}|$ 的舒适值。 现在有 $m$ 个人要来丑国旅游，第 $i$ 个人的丑值为 $x_i$，要从城市 $l_i$ 走到 $r_i$，问他得到的舒适值之和是多少。 **由于这个数可能很大，你需要求出对 $10^9+7$ 取模后的值**。 由于你不能预知到下一次旅游，我们会强制你在线。 **简化版题意：** 给出 $n$ 及 $n$ 个整数 $a_1,\,a_2,\,\dots,\,a_n$。 $m$ 次在线询问，每次询问给出 $x,\,l,\,r$，求 $\sum\limits_{i=l}^{r-1}|x-a_i|\times|x-a_{i+1}|$。

第一行输入两个整数 $n,m$，分别表示城市数与旅游人数。 第二行输入 $n$ 个整数，第 $i$ 个数表示 $a_i$，含义如上所述。 接下来 $m$ 行，每行输入三个整数 $X,\,L,\,R$，记上一次的旅游的总舒适值对 $10^9+7$ 取模后为 $s$（若是第一次询问，则 $s=0$），则 $x_i=X\operatorname{xor}s,\;l_i=L\operatorname{xor}s,\;r_i=R\operatorname{xor}s$，其中 $\operatorname{xor}$ 表示异或，而 $x_i,\,l_i,\,r_i$ 的含义如上所述。

输出 $m$ 行，第 $i$ 行的数表示第 $i$ 个人的总舒适值对 $10^9+7$ 取模后的值。

#### 样例说明： 对于第一次询问，从城 $1$ 走到城 $2$，获得舒适值为 $|1-1|\times|1-2|=0$；从城 $2$ 走到城 $3$，获得舒适值为 $|1-2|\times|1-3|=2$，故总舒适值为 $2$。 对于第二次询问，解密后的 $x,\,l,\,r$ 分别是 $4,3,5$。从城 $3$ 走到城 $4$，获得舒适值为 $|4-3|\times|4-4|=0$；从城 $4$ 走到城 $5$，舒适值为 $|4-4|\times|4-5|=0$，总舒适值为 $0$。 --- #### 数据范围： **本题采用捆绑测试。** | 编号 | 特殊限制 | 分值 |时限| | :-: | :-: | :-: |:-:| | Subtask0 | $n,\,m\le 10^4$ | 20pts |1s| | Subtask1 | $a_i,\,x\le 10$ | 10pts |2s| | Subtask2 | $a_i$ 单调递增 | 10pts |2s| | Subtask3 | 无特殊限制 | 60pts |2s| 对于 $100\%$ 的数据，$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$。