### 问题描述 农场笼罩在冬日的雪中，从农舍通向谷仓的小路上铺满了 $N$ 块砖，编号从1到$N$。每块砖上的积雪深度分别为 $f_i$。 在农舍的地下室里，小齐有 $B$ 双靴子，编号从1到$B$。每双靴子的性能各异，第 $i$ 双靴子让小齐能够在最深为 $s_i$ 的积雪中行走，并且每一步最多能够前进 $d_i$ 块砖。 小齐初始站在第1块砖上，他需要穿过这片雪地，走到第$N$块砖上唤醒正在谷仓里的奶牛。由于农舍和谷仓分别有屋顶遮挡，因此它们上面的积雪深度为 $0$。 帮助小齐确定使用哪些双靴子可以完成这次雪地之行。 ### 输入格式 第一行包含两个用空格分隔的整数 $N$ 和 $B$。 第二行包含 $N$ 个用空格分隔的整数，其中第 $i$ 个整数为 $f_i$ 表示第 $i$ 块砖上的积雪深度。保证 $f_1 = f_N = 0$。 接下来的 $B$ 行，每行包含两个用空格分隔的整数 $s_i$ 和 $d_i$，表示第 $i$ 双靴子的性能。 ### 输出格式 输出应包含 $B$ 行。第 $i$ 行应包含一个整数：如果小齐能够穿着第 $i$ 双靴子完成从第 $1$ 块砖到第$N$块砖的雪地之行，则输出 $1$；否则输出 $0$。 ### 样例输入 ``` 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 ``` ### 评测数据规模 $0 \leq f_i \leq 10^9$，$1 \leq N, B \leq 10^5$，$0 \leq s_i \leq 10^9$，$1 \leq d_i \leq N-1$。