Description
冬天到了，农场上又下起了雪。从农舍到牛棚一共有N块瓷砖，编号为1到N，第i块瓷砖上积雪的深度为fi英尺。
Farmer John一共有B双靴子，编号为1到B。一些靴子比较结实，一些靴子比较轻便，具体地说，第i双靴子能够让FJ在最多si英尺的积雪中每步最多前进di。
Farmer John必须从第一块瓷砖走到第N块瓷砖去叫醒奶牛们。第一块瓷砖在农舍的屋檐下，第N块瓷砖在牛棚的屋檐下，所以这两块砖上没有积雪。但是走在其他的瓷砖上时，Farmer John需要穿靴子了。
请帮助Farmer John求出哪些靴子可以帮助他走完这段艰辛的路程。
Input
第一行，用空格隔开的两个整数N和B（1≤N,B≤10^5）
第二行，用空格隔开的N个整数，第i个整数fi，表示第i块瓷砖上，积雪的深度（0≤fi≤10^9）.f1=fN=0
接下来B行，每行两个用空格隔开的整数si和di，描述第i双靴子能够承受的最大的积雪深度si和这双靴子能够最多向前步数di。（0≤si≤10^9,1≤di≤N-1）
Output
输出包含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