Stivali da neve (Oro)#10411
In fattoria è inverno, e questo significa neve! Il sentiero dalla casa del contadino al fienile è composto da piastrelle, numerate per comodità 1, \ldots, n, e la piastrella è coperta da uno strato di neve profondo f_i piedi.
Nella cantina della casa del contadino Giovanni sono conservati paia di stivali, numerati 1, \ldots, b. Alcuni paia sono più robusti di altri, mentre altri permettono di muoversi più agilmente. Precisamente, il paio permette al contadino Giovanni di camminare nella neve profonda al massimo s_i piedi e di avanzare al massimo di d_i piastrelle in un solo passo.
Il contadino Giovanni inizia il cammino dalla piastrella e deve raggiungere la piastrella per svegliare le mucche. La piastrella si trova sotto il tetto della casa del contadino, e la piastrella sotto il tetto del fienile, quindi su queste piastrelle non c'è neve. Aiuta il contadino Giovanni a determinare con quali paia di stivali potrà compiere questo tragitto.
Nella prima riga sono dati due numeri interi e b~(1 \le n, b \le 10^5).
Nella seconda riga sono dati numeri interi f_1, f_2, \ldots, f_n~(0 \le f_i \le 10^9), dove f_i è la profondità della neve sulla piastrella . È garantito che f_1 = f_n = 0.
Ciascuna delle successive righe contiene due numeri interi. La (i + 2)-esima riga contiene i numeri s_i e d_i~(0 \le s_i \le 10^9, 1 \le d_i \le n - 1) — rispettivamente la profondità massima di neve in cui si può camminare con il paio , e la lunghezza massima del passo con il paio .
Stampa righe. Nella -esima riga deve comparire un solo numero intero: , se il contadino Giovanni può arrivare dalla piastrella alla piastrella con l'-esimo paio di stivali, e in caso contrario.
Esempio 1