Ước mơ của Conan là được thăm quan nhà bạn gái một lần. Hôm nay, lấy cớ sắp thi, anh ấy quyết định qua nhà bạn gái để cùng nhau ôn tập cho kỳ thi sắp tới...

Nhưng khổ nổi, nhà anh thì ở trên núi, nhà em thì ở dưới thôn, cách nhau bởi những con đường dài ngoằn ngoèo với những ổ gà rộng và rất sâu. Thông qua việc tìm hiểu, Conan biết được rằng đoạn đường mà anh ấy cần vượt qua có chiều dài \(N\) mét, và anh ấy cũng biết được rằng với mỗi mét trên đường đi đều có ổ gà (riêng vị trí nhà của Conan và bạn gái ảnh là không có ổ gà, tương ứng với vị trí mét 1 và mét \(N\)). Để hỗ trợ cho việc di chuyển, Conan có \(M\) đôi giày, với đôi giày thứ \(i\) (\(1 \leq i \leq M\)) có đế giày cao \(H_{i}\) mét cho phép Conan đi được trên những ổ gà có độ sâu không vượt quá độ cao của đế giày, và đôi giày cũng cho phép anh tiến về phía trước xa nhất được \(D_{i}\) mét. Nhưng có tình yêu là mù quáng ngay, các bạn hãy giúp Conan xác định xem có thể đến nhà crush với đôi giày thứ \(i\) (\(1 \leq i \leq M\)) không nhé!.

Input

• Dòng đầu chứa hai số nguyên dương \(N\) và \(M\) (\(1 \leq N, M \leq {10 ^ 5}\)).
• Dòng thứ hai chứa \(N\) số nguyên không âm, số thứ \(i\) là \(F_{i}\), là độ sâu ổ gà thứ i (\(0 \leq F_{i} \leq {10 ^ 9}\)).
• \(M\) dòng tiếp theo, mỗi dòng chứa 2 số nguyên không âm \(H_{i}\) và \(D_{i}\), là độ cao đế giày thứ \(i\) và khoảng cách đi được xa nhất với mỗi bước di chuyển (\(0 \leq H_{i} \leq {10 ^ 9}\)) và (\(1 \leq D_{i} \leq N - 1\)).

Output

• In ra \(M\) dòng, mỗi dòng chỉ gồm số 1 hoặc 0 tương ứng với việc Conan có thể tới nhà bạn gái với đôi giày thứ \(i\) hay không.

Ví dụ

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