Online Comfort Value Query

In Ugly Country, there are n cities numbered from \(1\) to \(n\) arranged in a line. From city \(i\), one can only move to city \(i+1\). In each city \(i\), the residents dislike people whose ugliness value is \(a_i\). When a person with ugliness value \(x\) travels from city \(i\) to city \(i+1\), they gain a comfort value given by the formula:

[ |x-a_i|\times |x-a_{i+1}|, ]

You are given an array \(a_1, a_2, \dots, a_n\) and then \(m\) online queries. Each query provides three integers \(x, l, r\), where \(x\) is the ugliness value of the traveler, and the traveler goes from city \(l\) to city \(r\) (visiting every consecutive city along the path). For each query, compute the total comfort value:

[ S = \sum_{i=l}^{r-1} |x-a_i|\times |x-a_{i+1}| \mod (10^9+7). ]

Note: The queries are online, meaning you must process each query as it is received.

inputFormat

The first line contains two integers \(n\) and \(m\) — the number of cities and the number of queries.

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\), where \(a_i\) is the unfavored ugliness value at city \(i\).

This is followed by \(m\) lines, each containing three integers \(x, l, r\), representing a query.

outputFormat

For each query, output a single integer — the sum of the comfort values modulo \(10^9+7\).

sample

5 3
1 2 3 4 5
3 1 5
4 2 4
2 1 3

4
2
0