Codah ClubTrain. Submit. Improve.
Sign in
English
#000658

Bradonja

Captain Bradonja and his crew are the most terrifying pirates of the blue seas (and of those not so blue, polluted ones). One day, as they were searching a lost island for treasures they ran into a very hard problem, hard even for a pirate like Bradonja. Namely, the entrance to the cave in which the treasure lies is guarded by an angry fire demon who will not allow them to enter unless they correctly answer his questions. To make matters worse, if they give a wrong answer to at least one of his questions he will dispatch them all to hell. The demon drew a big convex polygon on the ground, marked all its corners and then said K times coordinates of a random dot in plane, and Bradonja and his crew are expected to tell him, for each dot, whether it is inside the polygon or not.


Help our hero and Bradonja will probably share his newly-gotten treasure with you! We hope so...



InputIn first row of the input there are two natural numbers N and K (3 \leq N \leq 100 000; 1 \leq K \leq 500 000).
In the next N rows there are N pairs of coordinates that represent corners of a convex polygon, given in counter-clockwise direction - each pair in a separate row. No two corners will have both coordinates the same.
In the next K rows there are pairs of coordinates representing dots in plane.
All coordinates will be natural numbers from interval [1, 60 000].


OutputFor each of the K rows in the input you need to output in separate rows either "1" (if the given point is inside the polygon) or "0" (if it is outside the polygon). If the point is exactly on the border of the polygon, we count as if it were inside.


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.