Given a positive integer k, two arrays are called k-similar if:

  * they are strictly increasing; 
  * they have the same length; 
  * all their elements are positive integers between 1 and k (inclusive); 
  * they differ in exactly one position. 



You are given an integer k, a strictly increasing array a and q queries. For each query, you are given two integers l_i ≤ r_i. Your task is to find how many arrays b exist, such that b is k-similar to array [a_{l_i},a_{l_i+1}…,a_{r_i}]. 

Input

The first line contains three integers n, q and k (1≤ n, q ≤ 10^5, n≤ k ≤ 10^9) — the length of array a, the number of queries and number k.

The second line contains n integers a_1, a_2, …,a_n (1 ≤ a_i ≤ k). This array is strictly increasing — a_1 < a_2 < … < a_n.

Each of the following q lines contains two integers l_i, r_i (1 ≤ l_i ≤ r_i ≤ n).

Output

Print q lines. The i-th of them should contain the answer to the i-th query.

Examples

Input


4 2 5
1 2 4 5
2 3
3 4


Output


4
3


Input


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


Output


8
9
7
6
9

Note

In the first example:

In the first query there are 4 arrays that are 5-similar to [2,4]: [1,4],[3,4],[2,3],[2,5].

In the second query there are 3 arrays that are 5-similar to [4,5]: [1,5],[2,5],[3,5].
def zip_sorted(a,b):

	# sorted  by a
	a,b = zip(*sorted(zip(a,b)))
	# sorted by b
	sorted(zip(a, b), key=lambda x: x[1])

	return a,b

def number_to_list(a):

	b = []

	while a>=1:

		c = a%10

		a = int(a/10)


		b.append(c)

	return list(reversed(b))

def str_list_to_int_list(a):


	a = list(map(int,a))

	return a

def make_1d_array(n,inti= 0):

	a = [inti for _ in range(n)]

	return a

def make_2d_array(n,m,inti= 0):

	a = [[inti for _ in range(m)] for _ in range(n)]

	return a

def make_3d_array(n,m,k,inti= 0):

	a = [[[inti for _ in range(k)] for _ in range(m)] for _ in range(n)]

	return a

def gcd(a,b):

	if(b==0): 
		return a

	else:
		return gcd(b,a%b);



import sys
input = sys.stdin.readline
I = lambda : list(map(int,input().split()))
S = lambda : list(map(str,input()))



n,q,k = I()
a   = I()
dp_start = [0]*n
dp_rest = [0]*n
dp_end = [0]*n
dp_sum = [0]*n
if n!=1:
	prev = -1
	for i in range(n):
		if i==0:
			dp_start[i] = a[i+1]-2
			dp_rest[i]  = a[i+1]-2
			dp_end[i]  = k-1
		elif i==n-1:
			dp_start[i] = k-1
			dp_rest[i]  = max(0,k-prev-2)			
			dp_end[i]  = max(0,k-prev-1)
		else:
			dp_start[i] = a[i+1]-2
			dp_rest[i]  = a[i+1]-prev-2
			dp_end[i]  = max(0,k-prev-1)
		prev = a[i]		
sum1 = 0
for i in range(len(dp_sum)):
	sum1 += dp_rest[i]
	dp_sum[i] = sum1

for  t1 in range(q):
	l1,r1   = I()
	if n==1:
		print(k-1)
	elif l1==r1:
		print(k-1)
	else:
		if r1-l1==1:
			print(dp_start[l1-1]+dp_end[r1-1])
		else:
			print(dp_start[l1-1]+dp_sum[r1-2]-dp_sum[l1-1]+dp_end[r1-1])

