21990_Mushroom-pickingsites

Mr. X knows the forest like the back of his hand and never returns emptyhanded when he goes out to pick mushrooms. This year, however, he was in for a surprise: part of the forest was fenced off and there was some sort of construction going on behind it...

Mr. X has provided you with a map of the forest with the fence around the construction site marked. Looking at the map, you can see that the fence is a polygon that does not intersect with itself. He, however, does not want to disclose the locations of the mushroom-picking sites... Therefore you have agreed that he will go to the forest and from time to time call you using his cell phone to ask if he can visit one or another place in the forest.

Write a program to answer his queries.

The first line contains N (3 ≤ N ≤ 100,000), the number of vertices of the polygon, and M (0 ≤ M ≤ 100,000), the number of queries. Each of the following N lines contains two integers in the range -100,000…100,000, the coordinates of the vertices of the polygon in the order in which they appear on the perimeter. It is known that the only common point between any two edges is the common endpoint they share if they are incident. Each of the following M lines also contains two integers in the range -100,000…100,000, the coordinates of the points Mr. X queries you about.

The output should consist of exactly M lines, one for each query. The line should contain the word Inside if the point queried about is inside the polygon, the word Outside if the point is outside the polygon, and the word Border if the point lies on an edge of the polygon.

4 4
1 2
3 -2
0 -1
-3 -2
2 0
1 -1
-2 1
1 2

Border
Inside
Outside
Border