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.
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).
Print — the answer of each query in a separate line
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 =10In second query id is greater than n after the first operation. So time is only 5In last query id is greater than n after the first operation. So time is only 5