길이가 N인 수열 a1, a2, ..., aN이 있다.
인접한 두 값 사이의 차이를 이용해, 어떤 구간의 변화량을 계산하려고 한다.

구간의 시작점이 i, 끝점이 j일 때, 그 구간의 변화량은 다음과 같이 정의한다.

sum from k = i to j-1 of |a(k+1) - ak|

만약 j - 1 < i인 경우에는 변화량을 0으로 본다.

기호 |a|는 임의의 실수 a에 대해 a < 0이면 |a| = -a이고, a ≥ 0이면 |a| = a임을 나타낸다.

여러 개의 구간이 주어질 때, 각 구간의 변화량을 구하는 프로그램을 작성하시오.

입력

입력의 첫 번째 줄에는 수열의 길이 N과 변화량의 합을 구해야 하는 구간의 수 Q가 공백으로 구분되어 주어진다.

입력의 두 번째 줄에는 순서대로 수열 a1, a2, ..., aN이 공백으로 구분되어 주어진다.

입력의 세 번째 줄부터 Q줄에 걸쳐 변화량의 합을 구해야 하는 구간의 시작점과 끝점이 주어진다.

출력

주어진 구간의 변화량의 합을 입력 순서대로 Q줄에 걸쳐 출력한다.

제한

• 1 ≤ N ≤ 1,000
• 1 ≤ Q ≤ 1,000
• -10^4 ≤ ai ≤ 10^4
• 1 ≤ l ≤ r ≤ N

예제 입력 1

4 3
100 101 382 573
1 1
1 3
2 4

예제 출력 1

0
282
472

예제 입력 2

5 3
1 0 1 0 -11
1 5
3 5
2 4

예제 출력 2

14
12
2