G. Balls and Pocketstime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputThere is a strip with an infinite number of cells. Cells are numbered starting with 0. Initially the cell i contains a ball with the number i.There are n pockets located at cells a_1, \ldots, a_n. Each cell contains at most one pocket.Filtering is the following sequence of operations: All pockets at cells a_1, \ldots, a_n open simultaneously, which makes balls currently located at those cells disappear. After the balls disappear, the pockets close again. For each cell i from 0 to \infty, if the cell i contains a ball, we move that ball to the free cell j with the lowest number. If there is no free cell j < i, the ball stays at the cell i.Note that after each filtering operation each cell will still contain exactly one ball.For example, let the cells 1, 3 and 4 contain pockets. The initial configuration of balls is shown below (underscores display the cells with pockets): 0 1 2 3 4 5 6 7 8 9 ... After opening and closing the pockets, balls 1, 3 and 4 disappear: 0   2     5 6 7 8 9 ... After moving all the balls to the left, the configuration looks like this: 0 2 5 6 7 8 9 10 11 12 ... Another filtering repetition results in the following: 0 5 8 9 10 11 12 13 14 15 ... You have to answer m questions. The i-th of these questions is "what is the number of the ball located at the cell x_i after k_i repetitions of the filtering operation?"InputThe first line contains two integers n and m — the number of pockets and questions respectively (1 \leq n, m \leq 10^5).The following line contains n integers a_1, \ldots, a_n — the numbers of cells containing pockets (0 \leq a_1 < \ldots < a_n \leq 10^9).The following m lines describe questions. The i-th of these lines contains two integers x_i and k_i (0 \leq x_i, k_i \leq 10^9).OutputPrint m numbers — answers to the questions, in the same order as given in the input.ExampleInput3 151 3 40 01 02 03 04 00 11 12 13 14 10 21 22 23 24 2Output0123402567058910
Input3 151 3 40 01 02 03 04 00 11 12 13 14 10 21 22 23 24 2
Output0123402567058910
['data structures', '*3400']