눈길 장화

농장에 겨울이 왔고, 눈이 내렸다. 농장 집에서 헛간까지 이어지는 길은 칸 $N$개로 이루어져 있고, 집 쪽부터 차례로 $1$번부터 $N$번까지 번호가 붙어 있다. $i$번 칸에는 눈이 $f_i$피트 쌓여 있다.

농부는 지하 창고에 장화 $B$켤레를 두고 있고, 각 켤레에 $1$번부터 $B$번까지 번호가 붙어 있다. 튼튼한 정도와 가벼운 정도는 켤레마다 다르다. $i$번 장화를 신으면 깊이가 $s_i$피트 이하인 눈을 밟을 수 있고, 한 걸음에 최대 $d_i$칸까지 앞으로 갈 수 있다.

농부는 소를 깨우려고 $1$번 칸에서 출발해 $N$번 칸까지 가야 한다. $1$번 칸은 집 지붕이, $N$번 칸은 헛간 지붕이 덮고 있어서 두 칸에는 눈이 쌓여 있지 않다.

한 걸음은 지금 서 있는 칸에서 $1$칸 이상 $d_i$칸 이하만큼 앞으로 옮기는 것이고, 발을 내려놓는 칸의 눈 깊이가 $s_i$ 이하여야 한다. 건너뛴 칸에 눈이 얼마나 쌓였는지는 상관없다. 장화 각 켤레마다 농부가 $1$번 칸에서 $N$번 칸까지 갈 수 있는지 판정하라.

첫째 줄에 정수 $N$과 $B$가 공백으로 구분되어 주어진다 ($1 \leq N, B \leq 10^5$).

둘째 줄에 정수 $N$개가 공백으로 구분되어 주어진다. $i$번째 정수는 $i$번 칸에 쌓인 눈의 깊이 $f_i$이다 ($0 \leq f_i \leq 10^9$). $f_1 = f_N = 0$임이 보장된다.

이어지는 $B$개 줄에는 정수가 두 개씩 공백으로 구분되어 주어진다. $i+2$번째 줄의 첫 번째 정수는 $i$번 장화로 밟을 수 있는 눈의 최대 깊이 $s_i$이고, 두 번째 정수는 $i$번 장화로 한 걸음에 갈 수 있는 최대 칸 수 $d_i$이다 ($0 \leq s_i \leq 10^9$, $1 \leq d_i \leq N-1$).

$B$개 줄을 출력한다. $i$번째 줄에는 $i$번 장화를 신고 $1$번 칸에서 $N$번 칸까지 갈 수 있으면 $1$을, 갈 수 없으면 $0$을 출력한다.