Codah ClubVježbaj. Pošalji. Napreduj.
Prijavi se
Hrvatski
#000658

Bradonja

Kapetan Bradonja i njegova posada su najstrašniji gusari na plavim morima (a i na onim drugih boja, zagađenim). Jednog dana dok su tražili blago na jednom pustom ostrvu naišli su na težak problem za jednog gusara, težak čak i za gusara poput Bradonje. Naime, ulaz u pećinu sa blagom čuva jedan ljuti vatreni demon koji im ne dozvoljava da prođu osim ako tačno odgovore na njegova pitanja. A da stvari budu gore, ukoliko pogrešno odgovore na bar jedno pitanje demon će ih sve odnijeti u pakao. Demon je na tlu nacrtao jedan veliki konveksan mnogougao, označio njegove vrhove koordinatama i onda K puta govori koordinate neke proizvoljne tačka a Bradonja i njegova posada moraju da tačno odgovore da li se ta tačka nalazi unutar nacrtanog mnogougla ili ne.


Pomozite našem junaku i Bradonja će vjerovatno podijeliti sa vama svoje novostečeno blago! Valjda...



InputU prvom redu se nalaze dva prirodna broja N i K (3 \leq N \leq 100 000; 1 \leq K \leq 500 000).
U sljedećih N redova se nalazi N parova koordinata koji predstavljaju vrhove konveksnog mnogougla, datih u smjeru suprotnom kretanju kazaljke na satu - svaki par u jednom redu. Nijedna dva vrha neće imati iste koordinate.
U sljedećih K redova se nalaze parovi koordinata koji predstavljaju pozicije tačaka u ravni.
Sve koordinate će biti prirodni brojevi iz intervala [1, 60 000].


OutputZa svaki od K redova sa ulaza ispišite u posebnom redu "1" (data tačka je unutar mnogougla) ili "0" (tačka se nalazi van mnogogugla). Smatramo da je tačka unutar mnogougla ako se nalazi na njegovom rubu.


Input
8 1
10 4
10 7
8 10
5 10
3 7
3 4
5 1
8 1
4 8
Output
1


Input
3 2
1 1
3 1
1 3
2 2
2 3
Output
1
0

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.