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