На ферме зима и много снега. Имеется \(N\) фрагментов на пути от фермы к амбару,
последовательно пронумерованных \(1 \dots N\), и фрагмент \(i\) покрыт \(f_i\)
футами снега.
В подвале у ФД имеется \(B\) пар ботов, пронумерованных \(1 \dots B\).
Некоторые потяжелее, а некоторые полегче. Пара \(i\) позволяет ФД идти по снегу
не более \(s_i\) футов глубиной и позволяет ФД сделать шаг длиной не более \(d_i\).
ФД начинает на фрагменте \(1\) и должен достичь фрагмента \(N\) чтобы разбудить
коров. Фрагмент \(1\) защищён крышей фермы, а фрагмент \(N\) защищён крышей амбара,
поэтому на них нет снега. Помогите ФД определить какую пару ботинок надеть, чтобы
пройти от фермы к амбару.
ФОРМАТ ВВОДА (файл snowboots.in):
Первая строка содержит два разделённых пробелом целых числа
\(N\) и
\(B\)
(
\(1 \leq N,B \leq 10^5\)).
Вторая строка содержит \(N\) целых чисел, разделённых одиночными пробелами.
\(i\)-ое число есть \(f_i\) - глубина снега на фрагменте \(i\) (\(0 \leq f_i \leq 10^9\)).
Гарантируется, что \(f_1 = f_N = 0\).
Каждая из следующих \(B\) строк содержат два разделённых пробелом целых числа.
Первое целое число есть \(s_i\) - максимальная глубина снега, в которую может ступить
пара \(i\). Второе целое число есть \(d_i\) - максимальный размер шага для пары \(i\).
Гарантируется, что \(0 \leq s_i \leq 10^9\) и \(1 \leq d_i \leq N-1\).
ФОРМАТ ВЫВОДА (файл snowboots.out):
Вывод должен состоять из \(N\) строк. Строка \(i\) должна содержать одно целое число
\(1\), если ФД может пройти от фрагмента \(1\) до фрагмента \(N\) надев \(i\)-ую пару ботинок,
и \(0\) в противном случае.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|