背景

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

题目描述

丑国的一角排列着编号从 $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$ 取模后的值。

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

2
0

提示

样例说明：

对于第一次询问，从城 $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$。

数据范围：

本题采用捆绑测试。

对于 $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$。