Minimum Energy Gathering

During a military training, students are required to gather at specified positions. There are n students with resting positions given by \(a_i\) on a number line. When a gathering command \((l, r, K)\) is issued, every student with index in the range \([l, r]\) must move to a distinct integer position within the interval \([K, K + (r-l)]\).

The physical effort for a student to move from position \(x\) to \(y\) is \(|y - x|\). The aim is to assign positions in \([K, K + (r-l)]\) to the students (each position used exactly once) in such a way that the total physical energy spent \(\sum |y - a_i|\) is minimized.

Note:

• Each command is independent. After each command, all students return to their original resting positions \(a_i\).
• If any student not in \([l, r]\) is found within the meeting interval, they will move away but their movement cost is not counted.

Task: Given the original positions of students and a series of commands, compute the minimum total physical energy required for each command.

inputFormat

The first line contains two integers \(n\) and \(m\) representing the number of students and the number of commands.

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) representing the resting positions of the students.

Each of the following \(m\) lines contains three integers \(l, r, K\), representing a command. For each command, students with indices from \(l\) to \(r\) (inclusive) must move to distinct positions in the interval \([K, K + (r-l)]\).

outputFormat

For each command, output a single line containing the minimum total energy spent by the students, assuming they choose positions optimally.

sample

5 3
1 5 3 2 4
1 3 10
2 5 0
1 5 -2

24
8
15