На ферме зима и много снега. Имеется n фрагментов на пути от фермы к амбару, последовательно пронумерованных 1...n, и фрагмент i покрыт fi футами снега.

В подвале у ФД имеется b пар ботов, пронумерованных 1..b. Некоторые потяжелее, а некоторые полегче. Пара i позволяет ФД идти по снегу не более si футов глубиной и позволяет ФД сделать шаг длиной не более di.

ФД начинает на фрагменте 1 и должен достичь фрагмента n чтобы разбудить коров. Фрагмент 1 защищён крышей фермы, а фрагмент n защищён крышей амбара, поэтому на них нет снега. Помогите ФД определить какую пару ботинок надеть, чтобы пройти от фермы к амбару.

Входные данные

Первая строка содержит два целых числа n и b (1 ≤ n, b ≤ 105).

Вторая строка содержит n целых чисел. i-ое число есть fi - глубина снега на фрагменте i (0 ≤ fi ≤ 109). Гарантируется, что f1 = fn = 0.

Каждая из следующих b строк содержат два целых числа. Первое целое число есть si - максимальная глубина снега, в которую может ступить пара i. Второе целое число есть di - максимальный размер шага для пары i. Гарантируется, что 0 ≤ si ≤ 109 и 1 ≤ di ≤ n − 1.

Выходные данные

Вывод должен состоять из n строк. Строка i должна содержать одно целое число 1, если ФД может пройти от фрагмента 1 до фрагмента n надев i-ую пару ботинок, и 0 в противном случае.