【题目描述】

到冬天了，这意味着下雪了！从农舍到牛棚的路上有 N 块地砖，方便起见编号为 1…N，第i块地砖上积了 fi 英尺的雪。在 Farmer John 的农舍的地窖中，总共 B 双靴子，编号为 1…B。其中某些比另一些结实，某些比另一些轻便。具体地说，第 i 双靴子能够让 FJ 在至多 si 英尺深的积雪中行走，能够让 FJ 每步至多前进 di。

Farmer John 从 1 号地砖出发，他必须到达 N 号地砖才能叫醒奶牛们。1 号地砖在农舍的屋檐下，N 号地砖在牛棚的屋檐下，所以这两块地砖都没有积雪。帮助 Farmer John 求出哪些靴子可以帮助他走完这段艰辛的路程。

【输入格式】

第一行包含两个空格分隔的整数 N 和 B（1≤N,B≤10^5）。第二行包含 N 个空格分隔的整数；第 i 个整数为 fi，即 i 号地砖的积雪深度（0≤fi≤10^9）。输入保证 f1=fN=0。

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

【输出格式】

输出包含 N 行。第 i 行包含一个整数：如果 Farmer John 能够穿着第 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

【来源】

USACO 2018 February Gold Snow Boots

供题：Dhruv Rohatgi