Powerful Array

You are given an array A of N integers . Now you have to process Q queries in this array. Each query is represented by two number id and K. You have to perform some operations for each query . Each operation is changes id to A[id]+K+id which take t time to do it. There operations are applied until id
becomes greater than n. In each query you have to print the total time is being taken to perform all
operation in each query.

Input

The first line of the input contains two integer N (1 ≤ N ≤ 20000) and t (1 ≤ t ≤ 10) denoting the size of the array and time.

Next line contain N integers Ai (1 ≤ Ai≤ N) which are the elements of the array.

Next line contains an integer Q (1 ≤ Q ≤ 105)denoting the number of queries.

Each of the following next Q line contains two integer id (1 ≤ id ≤ N) and K (1 ≤ K ≤ N).

Output

Print --- the answer of each query in a separate line

Sample

Input	Output
3 5 1 1 1 3 1 1 2 1 3 1	10 5 5
Consider first example: In first query after first operation id = 3, after second operation id = 5. Total Time = 2 * 5 =10 In second query id is greater than n after the first operation. So time is only 5 In last query id is greater than n after the first operation. So time is only 5