Shared code

//
// Created by michaelyang on 4:57 PM Jan 09 2022.
// Problem: pl in Polygon
// check if points are inside polygon

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
#include <map>

#define f first
#define s second
#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;

typedef long long ll;
typedef pair<ll,ll> pl;

const int MOD=1e9+7;
const int N=1e5+5;

string onSegment(pl p,pl q,pl r){
	if (q.f<max(p.f,r.f)&&q.f>min(p.f,r.f)&&q.s<max(p.s,r.s)&&q.s>min(p.s,r.s)) return "NOTON";
	if (((q.f==max(p.f,r.f)||q.f==min(p.f,r.f))&&(q.s<=max(p.s,r.s)&&q.s>=min(p.s,r.s)))||((q.f<=max(p.f,r.f)&&q.f>=min(p.f,r.f))&&(q.s==max(p.s,r.s)||q.s==min(p.s,r.s)))) return "ENDPOINT";
	return "ON";
}

// To find orientation of ordered triplet (p, q, r). 
// The function returns following values 
// 0 --> p, q and r are collinear 
// 1 --> Clockwise 
// 2 --> Counterclockwise 
int orientation(pl p,pl q,pl r){
	int val=(q.s-p.s)*(r.f-q.f)-
	        (q.f-p.f)*(r.s-q.s);

	if (val==0) return 0; // collinear
	return (val>0)?1:2; // clock or counterclock wise
}

// The function that returns true if line segment 'p1q1' 
// and 'p2q2' intersect. 
bool doIntersect(pl p1,pl q1,pl p2,pl q2){
	// Find the four orientations needed for general and 
	// special cases 
	int o1=orientation(p1,q1,p2);
	int o2=orientation(p1,q1,q2);
	int o3=orientation(p2,q2,p1);
	int o4=orientation(p2,q2,q1);

	// General case 
	if (o1!=o2&&o3!=o4)
		return true;

	// Special Cases 
	// p1, q1 and p2 are collinear and p2 lies on segment p1q1 
	if (o1==0&&onSegment(p1,p2,q1)=="ON") return true;

	// p1, q1 and p2 are collinear and q2 lies on segment p1q1 
	if (o2==0&&onSegment(p1,q2,q1)=="ON") return true;

	// p2, q2 and p1 are collinear and p1 lies on segment p2q2 
	if (o3==0&&onSegment(p2,p1,q2)=="ON") return true;

	// p2, q2 and q1 are collinear and q1 lies on segment p2q2 
	if (o4==0&&onSegment(p2,q1,q2)=="ON") return true;

	return false; // Doesn't fall in any of the above cases 
}

// Returns true if the pl p lies inside the polygon[] with n vertices 
string isInside(vector<pl> polygon,pl p){
	int n=polygon.size();
	// There must be at least 3 vertices in polygon[] 
	if (n<3) return "OUTSIDE";

	// Create a pl for line segment from p to infinite 
	pl extreme={1e9+5,p.s};

	// Count intersections of the above line with sides of polygon 
	int count=0,i=0;
	do{
		int next=(i+1)%n;

		// Check if the line segment from 'p' to 'extreme' intersects 
		// with the line segment from 'polygon[i]' to 'polygon[next]' 
		if (doIntersect(polygon[i],polygon[next],p,extreme)){
			// If the pl 'p' is collinear with line segment 'i-next', 
			// then check if it lies on segment. If it lies, return true, 
			// otherwise false 
			if (orientation(polygon[i],p,polygon[next])==0){
				if (onSegment(polygon[i],p,polygon[next])!="NOTON") return "BOUNDARY";
				else return "OUTSIDE";
			}
			count++;
		}
		i=next;
	} while (i!=0);

	// Return true if count is odd, false otherwise
	if (count%2) return "INSIDE";
	else return "OUTSIDE";
}

int main(){
	fastio
	int n,m;
	cin>>n>>m;
	vector<pl> polygon;
	for (int i=0;i<n;i++){
		int a,b;
		cin>>a>>b;
		polygon.push_back({a,b});
	}
	for (int i=0;i<m;i++){
		int a,b;
		cin>>a>>b;
		cout<<isInside(polygon,{a,b})<<endl;
	}
}