题目描述
In Mathematics arithmetic sequence is a sequence of numbers such that the difference between any two consecutive numbers is constant.
You are given a sequence A that consists of N integers: A1, A2, .., AN. You are allowed to do a single type of operation: increase or decrease an arbitrary element Ai exactly by 1.
Your task is calculate the minimum number of operations needed to change a substring A [L, R] into an arithmetic sequence in which two consecutive elements differ exactly by K. That means, after applying operations needed following condition should be satisfied: AL + 1 - AL = AL + 2 - AL + 1 = ... = AR - AR - 1 = K.
Input
The first line is T - the number of test cases. Then T test cases follow.
Each test consists of several lines. The first line consists of two integers N and K — the number of elements in the sequence A and the desired difference between two consecutive elements in arithmetic sequence. The second line contains N integer numbers A1, A2, .., AN. The next line contains a single integer Q — the number of queries you have to answer. Then Q lines follow, each containing two integers L and R.
Output
For every query print the minimum number of operations needed to change substring A [L, R] into an arithmetic sequence where any two consecutive elements differ exactly K.
Constraints
1 ≤ T ≤ 10
1 ≤ N ≤ 100000
0 ≤ K ≤ 10^8
-10^8 ≤ Ai ≤ 10^8
1 ≤ Q ≤ 100000
1 ≤ L ≤ R ≤ N
10% number of tests in which N, Q , K ≤ 10.
30% number of tests in which 1 ≤ N, Q ≤ 3000.
10% number of tests in which K = 0.
30% number of tests in which L = 1.
SAMPLE INPUT
2
3 1
1 1 3
2
1 1
1 3
5 2
1 2 3 4 5
3
4 5
1 3
1 5
SAMPLE OUTPUT
0
1
1
2
6
输入格式
见题面
输出格式
见题面