B'There 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: 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): After opening and closing the pockets, balls 1, 3 and 4 disappear: After moving all the balls to the left, the configuration looks like this: Another filtering repetition results in the following: 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?" The first line contains two integers n and m -- the number of pockets and questions respectively ( 1 <= q n, m <= q 10^5 ). The following line contains n integers a_1, ldots, a_n -- the numbers of cells containing pockets ( 0 <= q a_1 < ldots < a_n <= q 10^9 ). The following m lines describe questions. The i -th of these lines contains two integers x_i and k_i ( 0 <= q x_i, k_i <= q 10^9 ). Print m numbers -- answers to the questions, in the same order as given in the input. '...