# Practice on Toph

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

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

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 **A**_{i} (1 ≤ A_{i}≤ N) which are the elements of the array.

Next line contains an integer **Q** (1 ≤ Q ≤ 10^{5})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

Input | Output |
---|---|

3 5 1 1 1 3 1 1 2 1 3 1 | 10 5 5 |

Consider first example: |