Botas de nieve (Oro)#10411
¡En la granja es invierno, así que hay nieve! El camino desde la casa de la granja hasta el granero consta de losetas, numeradas convenientemente 1, \ldots, n, y la loseta está cubierta por una capa de nieve de profundidad f_i pies.
En el sótano de la casa de la granja, el granjero John guarda pares de botas, numerados 1, \ldots, b. Unos pares son más resistentes que otros, y otros permiten moverse con más agilidad. En concreto, el par permite al granjero John pisar en nieve de profundidad de hasta s_i pies y avanzar como máximo d_i losetas en un solo paso.
El granjero John comienza su camino en la loseta y debe llegar a la loseta para despertar a las vacas. La loseta está bajo el techo de la casa de la granja, y la loseta está bajo el techo del granero, por lo que en estas losetas no hay nieve. Ayuda al granjero John a determinar con cuáles pares de botas podrá realizar este recorrido.
En la primera línea se dan dos números enteros y b~(1 \le n, b \le 10^5).
En la segunda línea se dan números enteros f_1, f_2, \ldots, f_n~(0 \le f_i \le 10^9), donde f_i es la profundidad de la nieve en la loseta . Se garantiza que f_1 = f_n = 0.
Cada una de las siguientes líneas contiene dos números enteros. La línea (i + 2)-ésima contiene los números s_i y d_i~(0 \le s_i \le 10^9, 1 \le d_i \le n - 1) — respectivamente, la profundidad máxima de nieve en la que se puede pisar con el par de botas, y la longitud máxima de paso con el par de botas.
Imprime líneas. En la línea -ésima debe figurar un único número entero: si el granjero John puede llegar desde la loseta hasta la loseta con el -ésimo par de botas, y en caso contrario.
Ejemplo 1