Mùa đông đã đến ở trang trại, và điều đó có nghĩa là tuyết! Có \(N\) ô lát trên con đường từ nhà đến chuồng bò, được đánh số thuận tiện từ \(1 \dots N\), và ô \(i\) bị phủ bởi lớp tuyết sâu \(f_i\) feet.

Trong tầng hầm của ngôi nhà, bác nông dân John có \(B\) đôi ủng, được đánh số từ \(1 \dots B\). Một số đôi chịu được điều kiện khắc nghiệt hơn những đôi khác, còn một số đôi linh hoạt hơn những đôi khác. Cụ thể, đôi \(i\) cho phép bác nông dân John bước vào lớp tuyết sâu tối đa \(s_i\) feet và tiến về phía trước tối đa \(d_i\) ô trong mỗi bước.

Bác nông dân John bắt đầu tại ô \(1\) và phải đến ô \(N\) để đánh thức đàn bò. Ô \(1\) được mái nhà che chắn còn ô \(N\) được mái chuồng che chắn, nên cả hai ô này đều không có tuyết. Hãy giúp bác nông dân John xác định những đôi ủng tuyết nào cho phép ông thực hiện hành trình này.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(B\) cách nhau bởi dấu cách (\(1 \leq N,B \leq 10^5\)).

Dòng thứ hai chứa \(N\) số nguyên cách nhau bởi dấu cách; số nguyên thứ \(i\) là \(f_i\), độ sâu của tuyết trên ô \(i\) (\(0 \leq f_i \leq 10^9\)). Bảo đảm rằng \(f_1 = f_N = 0\).

\(B\) dòng tiếp theo, mỗi dòng chứa hai số nguyên cách nhau bởi dấu cách. Số nguyên đầu tiên trên dòng \(i+2\) là \(s_i\), độ sâu tuyết lớn nhất mà đôi ủng \(i\) có thể bước vào. Số nguyên thứ hai trên dòng \(i+2\) là \(d_i\), độ dài bước chân lớn nhất của đôi ủng \(i\). Bảo đảm rằng \(0 \leq s_i \leq 10^9\) và \(1 \leq d_i \leq N-1\).

Dữ liệu ra

Kết quả gồm \(B\) dòng. Dòng \(i\) chứa một số nguyên duy nhất: \(1\) nếu bác nông dân John có thể đi từ ô \(1\) đến ô \(N\) khi mang đôi ủng thứ \(i\), và \(0\) nếu không thể.

Ví dụ

8 7
0 3 8 5 6 9 0 0
0 5
0 6
6 2
8 1
10 1
5 3
150 7

0
1
1
0
1
1
1

Nguồn

USACO 2018 February Contest, Gold — Snow Boots

Tác giả bài toán: Dhruv Rohatgi.