Снігові чоботи (Золото)#10411
На фермі зима, а отже — сніг! Доріжка від фермерського будинку до сараю складається з плиток, для зручності пронумерованих 1, \ldots, n, і плитка вкрита шаром снігу глибиною f_i футів.
У підвалі фермерського будинку фермер Джон зберігає пар чобіт, пронумерованих 1, \ldots, b. Одні пари міцніші за інші, а інші дозволяють пересуватися спритніше. А саме, пара дозволяє фермеру Джону ступати в сніг глибиною не більше s_i футів і просуватися вперед не більше ніж на d_i плиток за один крок.
Фермер Джон починає шлях із плитки і повинен дістатися до плитки , щоб розбудити корів. Плитка знаходиться під дахом фермерського будинку, а плитка — під дахом сараю, тому на цих плитках снігу немає. Допоможіть фермеру Джону визначити, в яких парах чобіт він зможе здійснити цей перехід.
У першому рядку задані два цілих числа і b~(1 \le n, b \le 10^5).
У другому рядку задані цілих чисел f_1, f_2, \ldots, f_n~(0 \le f_i \le 10^9), де f_i — глибина снігу на плитці . Гарантується, що f_1 = f_n = 0.
Кожен з наступних рядків містить два цілих числа. (i + 2)-й рядок містить числа s_i та d_i~(0 \le s_i \le 10^9, 1 \le d_i \le n - 1) — відповідно максимальну глибину снігу, в який можна ступати в парі , та максимальну довжину кроку в парі .
Виведіть рядків. У -му рядку має бути одне ціле число: , якщо фермер Джон може дістатися від плитки до плитки у -й парі чобіт, та у протилежному випадку.
Приклад 1