WLD is always very lucky.His secret is a lucky number . is a fixed odd number. Now he meets a stranger with numbers:.The stranger asks him questions.Each question is like this:Given two ranges and ,you can choose two numbers and to make .The you can choose is between and and the you can choose is between and .How many pairs of numbers you can choose?
If WLD can answer all the questions correctly,he'll be the luckiest man in the world.Can you help him?
Input
There are multiple cases.(At MOST )

For each case:

The first line contains an integer .

The following line contains an integer ,WLD's lucky number.K is odd.

The following line contains integers .

The following line contains an integer ,the sum of the questions WLD has to answer.

The following lines,the i-th line contains numbers ,describing the i-th question the stranger asks.
Output
For each case:

Print the total of pairs WLD can choose for each question.
Sample Input
5
3
1 2 1 2 3
1
1 2 3 5
Sample Output
2

Hint
a1+a4=a2+a3=3=K.
So we have two pairs of numbers (1,4) and (2,3).
Good luck!

题意：

给你一个长度为n的数组a，以及一个整数k，和m个询问。

每一个询问给你两个区间分别是 l~r，u~v，

问你有多少对 x，y 满足 a[x]+a[y]=k 并且 l<=x<=r, u<=y<=v