Снежные ботинки (Золото)
На ферме зима и много снега. Имеется n фрагментов на пути от фермы к амбару, последовательно пронумерованных 1...n, и фрагмент i покрыт f[i] футами снега.
В подвале у ФД имеется b пар ботов, пронумерованных 1..b. Некоторые потяжелее, а некоторые полегче. Пара i позволяет ФД идти по снегу не более s[i] футов глубиной и позволяет ФД сделать шаг длиной не более d[i].
ФД начинает на фрагменте 1 и должен достичь фрагмента n чтобы разбудить коров. Фрагмент 1 защищён крышей фермы, а фрагмент n защищён крышей амбара, поэтому на них нет снега. Помогите ФД определить какую пару ботинок надеть, чтобы пройти от фермы к амбару.
Входные данные
Первая строка содержит два целых числа n и b (1 ≤ n, b ≤ 10^5).
Вторая строка содержит n целых чисел. i-ое число есть f[i] - глубина снега на фрагменте i (0 ≤ f[i] ≤ 10^9). Гарантируется, что f[1] = f[n] = 0.
Каждая из следующих b строк содержат два целых числа. Первое целое число есть s[i] - максимальная глубина снега, в которую может ступить пара i. Второе целое число есть d[i] - максимальный размер шага для пары i. Гарантируется, что 0 ≤ s[i] ≤ 10^9 и 1 ≤ d[i] ≤ n − 1.
Выходные данные
Вывод должен состоять из n строк. Строка i должна содержать одно целое число 1, если ФД может пройти от фрагмента 1 до фрагмента n надев i-ую пару ботинок, и 0 в противном случае.