Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Powerful Array

By Limon_88 · Limits 1s, 512 MB

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

InputOutput
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


Discussion

Statistics


100% Solution Ratio

Arl_88Earliest, 1M ago

Arl_88Fastest, 0.1s

Arl_88Lightest, 26 MB

Arl_88Shortest, 1179B

Submit

Login to submit

Related Contests

SEC Intra Campus Programming Contest, CSE Fest 2020 Ended at 2020-02-19 11:02:00 +0000 UTC