Снежные ботинки (Золото)
Снежные ботинки (Золото)
На ферме зима и много снега. Имеется 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 в противном случае.
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