As a university student, Kujou Karen participated in the last military training of her life last year.

One of the important projects in military training is practicing formation. To train the students, the instructor assigns a resting position to each student. Before each training session, all students rest at their respective resting positions, but when the instructor issues a gathering command, the called students must gather at a designated location.

To simplify the problem, we represent the resting positions and the gathering location on a number line. There are $n$ students in total, and the resting position of the $i$-th student is $a_i$. For each command, the instructor specifies an interval $[l, r]$ and a gathering point $K$. All students with indices in $[l, r]$ must rush to the gathering point to form a line. When forming the line, each student must choose an integer coordinate in $[K, K + r - l]$ such that no two students choose the same coordinate. A student consumes $|y - x|$ physical energy to run from coordinate $x$ to coordinate $y$.

During a day of training, the instructor issues $m$ commands $(l, r, K)$. You need to calculate, for each command, the minimum total physical energy consumed among all possible formation schemes.

Supplementary explanation: Any two commands are independent, meaning that after a gathering command ends, all students return to their own resting positions before the instructor issues the next command. When gathering, some students whose indices are not in $[l, r]$ might be located in the interval $[K, K + r - l]$. In this case, they will run away on their own, and the distance they run is not counted in the total physical energy consumption.

Input

The first line contains two integers $n, m$. The second line contains $n$ integers $a_i$, representing the resting positions of the students. It is guaranteed that the students' resting positions are distinct. The following $m$ lines each contain three integers $l, r, K$, representing a command.

Output

For each command, output a single integer on a new line, representing the sum of physical energy consumed by each student in the formation scheme that minimizes the total energy consumption for that command.

Examples

Input 1

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

Output 1

5
4
17
9
3

Note

In the first command, the five students run to $[2, 5, 4, 6, 3]$ respectively, so the cost is $|2 - 1| + |5 - 5| + |4 - 7| + |6 - 6| + |3 - 2| = 5$. In the second command, the five students run to $[4, 5, 7, 6, 3]$ respectively, so the cost is $|4 - 1| + |5 - 5| + |7 - 7| + |6 - 6| + |3 - 2| = 4$. In the third command, the three students run to $[11, 10, 9]$ respectively, so the cost is $|11 - 1| + |10 - 5| + |9 - 7| = 17$. In the fourth command, the three students run to $[4, 2, 3]$ respectively, so the cost is $|4 - 5| + |2 - 7| + |3 - 6| = 9$. In the fifth command, the three students run to $[7, 6, 5]$ respectively, so the cost is $|7 - 7| + |6 - 6| + |5 - 2| = 3$.

Constraints

For 10% of the data, $n, m \le 10$. For 40% of the data, $n, m \le 10^3$. For 70% of the data, $n, m \le 10^5$. For 100% of the data, $n, m \le 5 \cdot 10^5$, $1 \le a_i, K \le 10^6$, and the students' resting positions are distinct.