Snow Boots (Gold)#10411
It's winter on the farm, and that means snow! There are tiles on the path from the farmhouse to the barn, conveniently numbered 1, \ldots, n, and tile is covered with f_i feet of snow.
In his farmhouse cellar, Farmer John has pairs of boots, numbered 1, \ldots, b. Some pairs are more heavy-duty than others, and some are more agile than others. Specifically, pair allows Farmer John to step in snow at most s_i feet deep and to move forward by at most d_i tiles in a single step.
Farmer John starts on tile and must reach tile to wake up the cows. Tile is sheltered by the farmhouse roof, and tile is sheltered by the barn roof, so neither of these tiles has any snow. Help Farmer John determine which pairs of boots will allow him to make the trek.
The first line contains two integers and b~(1 \le n, b \le 10^5).
The second line contains integers f_1, f_2, \ldots, f_n~(0 \le f_i \le 10^9), where f_i is the depth of snow on tile . It is guaranteed that f_1 = f_n = 0.
Each of the next lines contains two integers. The (i + 2)-th line contains s_i and d_i~(0 \le s_i \le 10^9, 1 \le d_i \le n - 1) — the maximum depth of snow in which pair can step and the maximum step length for pair , respectively.
Print lines. The -th line should contain one integer: if Farmer John can get from tile to tile wearing the -th pair of boots, and otherwise.
Example 1