题目描述

处理完所有的红包之后，王洋老师决定给所有即将奋战在教学岗位的老师们也发一个开工红包但是，在从家里去单位路上王老师被一场大雪封住了道路。

从家里去单位路上有 $N$ 块地砖，方便起见编号为 $1 \dots N$，第 $i$ 块地砖上积了 $f_i$ 英尺的雪。

王老师总共珍藏了 $B$ 双靴子，编号为 $1 \dots B$。其中某些比另一些结实，某些比另一些轻便。具体地说，第 $i$ 双靴子能够让 FJ 在至多 $s_i$ 英尺深的积雪中行走，能够让 FJ 每步至多前进 $d_i$。

王老师 从 $1$ 号地砖出发，他必须到达 $N$ 号地砖才能成功发放开工红包。$1$ 号地砖在家门口，$N$ 号地砖在单位门口，所以这两块地砖都没有积雪。帮助王老师求出哪些靴子可以帮助他走完这段艰辛的路程。

输入格式

第一行包含两个空格分隔的整数 $N$ 和 $B$（$1 \leq N,B \leq 10^5$）。

第二行包含$N$个空格分隔的整数；第 $i$ 个整数为 $f_i$，即 $i$ 号地砖的积雪深度（$0 \leq f_i \leq 10^9$）。输入保证 $f_1 = f_N = 0$。

下面 $B$ 行，每行包含两个空格分隔的整数。第 $i+2$ 行的第一个数为 $s_i$，表示第 $i$ 双靴子能够承受的最大积雪深度。第 $i+2$ 行的第二个数为 $d_i$，表示第 $i$ 双靴子的最大步长。输入保证 $0 \leq s_i \leq 10^9$ 以及 $1 \leq d_i \leq N-1$。

输出格式

输出包含 $B$ 行。第 $i$ 行包含一个整数：如果王老师能够穿着第 $i$ 双靴子从 $1$ 号地砖走到 $N$ 号地砖，为 $1$，否则为 $0$。

输入输出样例 #1

输入 #1

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

输出 #1

0
1
1
0
1
1
1