Trời mưa to làm cho con đường vượt qua một khúc suối vốn đang cạn ngập nước. Có thể mô tả con đường này là một dãy gồm n vị trí đánh số \(1, 2, ...\), ; hai vị trí liên tiếp cách nhau 1 đơn vị. Vị trí thứ \(i\) hiện đang bị ngập sâu \(a_i\) đơn vị nước.

Ron muốn vượt qua con suối ngập nước này bằng cách di chuyển trên con đường nói trên (vì cậu ta chưa đủ 17 tuổi nên không được dùng phép thuật). May mắn là trong ba lô của Ron có m đôi ủng thần kỳ vốn là quà tặng sinh nhật của Hemione. Đôi ửng thứ \(i\) giúp Ron có thể đứng được ở vị trí ngập không quá \(b_i\) đơn vị nước và cho phép cậu ta mỗi bước di chuyển tối đa \(d_i\) đơn vị từ vị trí đang đứng.

Bờ suối nơi Ron đứng là vị trí \(1\) còn bờ bên kia - nơi Ron cần đến là vị trí \(n\) không bị ngập nước. Hãy giúp Ron xác định xem những đôi ủng nào có thể giúp cậu ta di chuyển qua suối.

Input:

• Dòng đầu tiên chứa hai số nguyên dương \(n,m (1≤n, m≤10^5)\)

• Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,…,a_n (0≤a_i≤ 10^9)\). Chú ý rằng \(a_1=a_n=0\)

• \(m\) dòng tiếp theo mô tả các đôi ủng . Dòng thứ \(i\) mô tả đôi ủng thứ i gồm hai số nguyên \(b_i\) - độ sâu ngập nước tối đa mà đôi ủng này có thể đứng được và \(d_i\) - khoảng cách xa tối đa của một bước.

Output:

• In ra \(m\) dòng. Dòng thứ \(i\) ghi số \(1\) nếu như đôi ủng thứ \(i\) có thể được dùng để vượt qua suối và chứa số \(0\) nếu như không thể dùng được.

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