B'Given a positive integer k , two arrays are called k -similar if: You are given an integer k , a strictly increasing array a and q queries. For each query, you are given two integers l_i <= q 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} ldots,a_{r_i}] . The first line contains three integers n , q and k ( 1 <= q n, q <= q 10^5 , n <= q k <= q 10^9 ) -- the length of array a , the number of queries and number k . The second line contains n integers a_1, a_2, ldots,a_n ( 1 <= q a_i <= q k ). This array is strictly increasing -- a_1 < a_2 < ldots < a_n . Each of the following q lines contains two integers l_i , r_i ( 1 <= q l_i <= q r_i <= q n ). Print q lines. The i -th of them should contain the answer to the i -th query. 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] . '...