It's winter on the farm, and that means snow! There are NN
tiles on the path from the farmhouse to the barn, conveniently numbered 1…N1…N
, and tile ii
is covered in fifi
feet of snow.
In his farmhouse cellar, Farmer John has BB pairs of boots, numbered 1…B1…B. Some pairs are more heavy-duty than others, and some pairs are more agile than others. In particular, pair ii lets FJ step in snow at most sisi feet deep, and lets FJ move at most didi forward in each step.
Farmer John starts off on tile 11 and must reach tile NN to wake up the cows. Tile 11 is sheltered by the farmhouse roof, and tile NN is sheltered by the barn roof, so neither of these tiles has any snow. Help Farmer John determine which pairs of snow boots will allow him to make the trek.
INPUT FORMAT (file snowboots.in):
The first line contains two space-separated integers N and B (1≤N,B≤105).
The second line contains NN space-separated integers; the iith integer is fifi, the depth of snow on tile i (0≤fi≤109). It's guaranteed that f1=fN=0.
The next BB lines contain two space-separated integers each. The first integer on line i+2i+2 is sisi, the maximum depth of snow in which pair ii can step. The second integer on line i+2 is di, the maximum step size for pair i. It's guaranteed that 0≤si≤109 and 1≤di≤N−1.
OUTPUT FORMAT (file snowboots.out):
The output should consist of BB lines. Line ii should contain a single integer: 11 if Farmer John can trek from tile 11 to tile NN wearing the iith pair of boots, and 00 otherwise.
SAMPLE INPUT:
8 7
0 3 8 5 6 9 0 0
0 5
0 6
6 2
8 1
10 1
5 3
150 7
SAMPLE OUTPUT:
0
1
1
0
1
1
1