Laiko ribojimas: 1s

Atminties ribojimas: 256MB

Duomenų failas: balos.in

Rezultatų failas: balos.out

Jei norite pateikti savo sprendimą - prisijunkite.

Balos

"Ir vėl pavasaris", - pagalvojo Mantas niūriai spoksodamas pro langą į kieme telkšančias balas.

-- Mantelio, būk žmogus, nubėk į malkinę ir parnešk kelias malkas židiniui užsikurti,- išgirdo iš gretimo kambario sklindantį senelio balsą.

Mantas žvilgtelėjo į pilną balų kelią nuo namų iki malkinės ir galiausiai nuėjo ieškoti tinkamų batų.

Nuo namo iki malkinės yra išdėstyta N plytelių dar nuo Manto vaikystės sunumeruotų nuo 1 iki N. Kiekviena plytelė yra netolygiai įsmukusi sudarydama F_i gylio balą.

Mantas turi B batų porų, taipogi sunumeruotų nuo 1 iki B (Mantui nepatinka, jei daiktai nėra sunumeruoti). Su i-tąja batų pora Mantas gali įlipti į S_i gylio balą bei pereiti iki D_i plytelių į priekį. Mantas pradeda savo kelionę nuo pirmos plytelės ir turi pasiekti N-tąją plytelę, kad patektų į malkinę. Padėkite Mantui sužinoti, su kuriom batų porom jis gali nusigauti iki malkinės.

Pradiniai duomenys

Pirmoje eilutėje yra skaičiai N ir B (1\\leqN,B\\leq10^5) - plytelių bei batų porų skaičius.

Antroje eilutėje yra N skaičių F_i (1\\leqF_i\\leq10^9) - i-tosios plytelės vietoje esančios balos gylis.

Sekančiose B eilučių yra po du skaičius S_i bei D_i - į kokio maksimalaus gylio balą gali įlipti Jonas avėdamas i-tuosius batus bei per kiek daugiausia plytelių gali pereiti vienu žingsniu.

Rezultatai

Išveskite B eilučių - kiekvienai batų porai po vieną skaičių: 1 - jei su i-tąja pora Mantas gali pasiekti malkinę, kitu atveju 0.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
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