#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<vector>
#define inf 1000000000
#define eps 1e-10
#define double long double
using namespace std;
struct point{
	double x,y;
	void read(){scanf("%Lf%Lf",&x,&y);}
	void write(){printf("%.10Lf %.10Lf\n",x,y);}
	point(double X=0.0,double Y=0.0):x(X),y(Y){}
	point operator +(const point a)const{return point(x+a.x,y+a.y);}
	point operator -(const point a)const{return point(x-a.x,y-a.y);}
	point operator *(double a)const{return point(x*a,y*a);}
	point operator /(double a)const{return point(x/a,y/a);}
	bool operator ==(const point a)const{return abs(x-a.x)<=eps && abs(y-a.y)<=eps;}
};
double dis(point a,point b=point(0,0)){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
double dot(point a,point b){return a.x*b.x+a.y*b.y;}
double cross(point a,point b){return a.x*b.y-a.y*b.x;}
double cross3(point o,point a,point b){return cross(a-o,b-o);}
bool jiao(point a,point b,point c,point d)
{
	if(min(a.x,b.x)>max(c.x,d.x) || min(a.y,b.y)>max(c.y,d.y)) return false;
	if(min(c.x,d.x)>max(a.x,b.x) || min(c.y,d.y)>max(a.y,b.y)) return false;
	if(cross3(a,b,c)*cross3(a,b,d)>0) return false;
	if(cross3(c,d,a)*cross3(c,d,b)>0) return false;
	return true;
}
short int on_line(point o,point a,point b)//oa->ob 0:D 1:U 2:O
{
	if(dot(a-o,b-o)<-eps) return 0;
	return 1+(dis(a-o)>=dis(b-o));
}
void make_rand(double &x){x=x+(1ll*rand()%10+1)/10.0*eps;}
struct Line{
	point a,b;
	Line(point x=point(0,0),point y=point(0,0)):a(x),b(y){}
	void read(){a.read();b.read();}
	bool operator &&(const Line u){return jiao(a,b,u.a,u.b);}
	point operator &(const Line u)
	{
		if(a==u.a || a==u.b) return a;
		if(b==u.a || b==u.b) return b;
		double x1=a.x,x2=b.x,x3=u.a.x,x4=u.b.x;
		double y1=a.y,y2=b.y,y3=u.a.y,y4=u.b.y;
		if(x3==x4) return point(x3,(y2-y1)*x3/(x2-x1)+(y1*x2-x1*y2)/(x2-x1));
		if(x1==x2) return point(x1,(y4-y3)*x1/(x4-x3)+(y3*x4-x3*y4)/(x4-x3));
		make_rand(x2);
		double x=((y3*x4-y4*x3)*(x2-x1)-(y1*x2-y2*x1)*(x4-x3))/((y2-y1)*(x4-x3)-(y4-y3)*(x2-x1));
		double y=(y2-y1)*x/(x2-x1)+(y1*x2-x1*y2)/(x2-x1);
		return point(x,y);
	}
};
point project(Line a,point p)
{
	point &p1=a.a,&p2=a.b;
	double len=dot(p2-p1,p-p1)/dis(p2-p1);
	return p1+(p2-p1)/dis(p2-p1)*len;
}
double dis(Line a,Line b)
{
	if(a && b) return 0;
	double ans=min(min(dis(a.a,b.a),dis(a.a,b.b)),min(dis(a.b,b.a),dis(a.b,b.b)));
	point res=project(a,b.a);
	if(on_line(a.a,a.b,res)==2) ans=min(ans,dis(res,b.a));
	res=project(a,b.b);
	if(on_line(a.a,a.b,res)==2) ans=min(ans,dis(res,b.b));
	res=project(b,a.a);
	if(on_line(b.a,b.b,res)==2) ans=min(ans,dis(res,a.a));
	res=project(b,a.b);
	if(on_line(b.a,b.b,res)==2) ans=min(ans,dis(res,a.b));
	return ans;
}
struct polygon{
	vector<point>p;
	void read(int n=-1)
	{
		if(n<0) scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			point a;
			a.read();
			p.push_back(a);
		}
	}
	double area(void)
	{
		double ans=0;
		for(int i=1;i<p.size();i++)
		ans+=cross3(p[0],p[i-1],p[i])/2;
		return abs(ans);
	}
	bool convex(void)
	{
		short int right=-1;
		for(int i=2;i<p.size();i++)
		if(right<0) right=cross3(p[i-2],p[i-1],p[i])>=0;
		else if(right!=(cross3(p[i-2],p[i-1],p[i])>=0)) return false;
		if(right!=(cross3(p[p.size()-2],p[p.size()-1],p[0])>=0)) return false;
		return true;
	}
	short int in_polygon(const point x)
	{
		Line l(x,x+point(inf,(double)inf*1.414213562373));
		make_rand(l.b.y);
		int cnt=0;
		for(int i=1;i<p.size();i++)
		{
			Line u(p[i-1],p[i]);
			if(u && l)
			{
				cnt++;
				if(abs(cross3(p[i-1],p[i],x))<eps && on_line(p[i-1],p[i],x)==2) return 1;
			}
		}
		Line u(p[p.size()-1],p[0]);
		if(u && l)
		{
			cnt++;
			if(abs(cross3(p[p.size()-1],p[0],x))<eps && on_line(p[p.size()-1],p[0],x)==2) return 1;
		}
		return cnt%2==0?0:2; 
	}
}p;
int main()
{
	int n;
	scanf("%d",&n);
	
	srand(n);
	p.read(n);
	int q;
	scanf("%d",&q);
	while(q--)
	{
		point x;
		x.read();
		printf("%d\n",p.in_polygon(x));
	}
	return 0;
}


### Prompt

Please formulate a cpp solution to the following problem:

For a given polygon g and target points t, print "2" if g contains t, "1" if t is on a segment of g, "0" otherwise.

g is represented by a sequence of points p1, p2,..., pn where line segments connecting pi and pi+1 (1 ≤ i ≤ n-1) are sides of the polygon. The line segment connecting pn and p1 is also a side of the polygon.

Note that the polygon is not necessarily convex.

Constraints

* 3 ≤ n ≤ 100
* 1 ≤ q ≤ 1000
* -10000 ≤ xi, yi ≤ 10000
* No point of the polygon will occur more than once.
* Two sides of the polygon can intersect only at a common endpoint.

Input

The entire input looks like:


g (the sequence of the points of the polygon)
q (the number of queris = the number of target points)
1st query
2nd query
:
qth query


g is given by coordinates of the points p1,..., pn in the following format:


n
x1 y1
x2 y2
:
xn yn


The first integer n is the number of points. The coordinate of a point pi is given by two integers xi and yi. The coordinates of points are given in the order of counter-clockwise visit of them.

Each query consists of the coordinate of a target point t. The coordinate is given by two intgers x and y.

Output

For each query, print "2", "1" or "0".

Example

Input

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


Output

2
1
0

### Response

```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<vector>
#define inf 1000000000
#define eps 1e-10
#define double long double
using namespace std;
struct point{
	double x,y;
	void read(){scanf("%Lf%Lf",&x,&y);}
	void write(){printf("%.10Lf %.10Lf\n",x,y);}
	point(double X=0.0,double Y=0.0):x(X),y(Y){}
	point operator +(const point a)const{return point(x+a.x,y+a.y);}
	point operator -(const point a)const{return point(x-a.x,y-a.y);}
	point operator *(double a)const{return point(x*a,y*a);}
	point operator /(double a)const{return point(x/a,y/a);}
	bool operator ==(const point a)const{return abs(x-a.x)<=eps && abs(y-a.y)<=eps;}
};
double dis(point a,point b=point(0,0)){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
double dot(point a,point b){return a.x*b.x+a.y*b.y;}
double cross(point a,point b){return a.x*b.y-a.y*b.x;}
double cross3(point o,point a,point b){return cross(a-o,b-o);}
bool jiao(point a,point b,point c,point d)
{
	if(min(a.x,b.x)>max(c.x,d.x) || min(a.y,b.y)>max(c.y,d.y)) return false;
	if(min(c.x,d.x)>max(a.x,b.x) || min(c.y,d.y)>max(a.y,b.y)) return false;
	if(cross3(a,b,c)*cross3(a,b,d)>0) return false;
	if(cross3(c,d,a)*cross3(c,d,b)>0) return false;
	return true;
}
short int on_line(point o,point a,point b)//oa->ob 0:D 1:U 2:O
{
	if(dot(a-o,b-o)<-eps) return 0;
	return 1+(dis(a-o)>=dis(b-o));
}
void make_rand(double &x){x=x+(1ll*rand()%10+1)/10.0*eps;}
struct Line{
	point a,b;
	Line(point x=point(0,0),point y=point(0,0)):a(x),b(y){}
	void read(){a.read();b.read();}
	bool operator &&(const Line u){return jiao(a,b,u.a,u.b);}
	point operator &(const Line u)
	{
		if(a==u.a || a==u.b) return a;
		if(b==u.a || b==u.b) return b;
		double x1=a.x,x2=b.x,x3=u.a.x,x4=u.b.x;
		double y1=a.y,y2=b.y,y3=u.a.y,y4=u.b.y;
		if(x3==x4) return point(x3,(y2-y1)*x3/(x2-x1)+(y1*x2-x1*y2)/(x2-x1));
		if(x1==x2) return point(x1,(y4-y3)*x1/(x4-x3)+(y3*x4-x3*y4)/(x4-x3));
		make_rand(x2);
		double x=((y3*x4-y4*x3)*(x2-x1)-(y1*x2-y2*x1)*(x4-x3))/((y2-y1)*(x4-x3)-(y4-y3)*(x2-x1));
		double y=(y2-y1)*x/(x2-x1)+(y1*x2-x1*y2)/(x2-x1);
		return point(x,y);
	}
};
point project(Line a,point p)
{
	point &p1=a.a,&p2=a.b;
	double len=dot(p2-p1,p-p1)/dis(p2-p1);
	return p1+(p2-p1)/dis(p2-p1)*len;
}
double dis(Line a,Line b)
{
	if(a && b) return 0;
	double ans=min(min(dis(a.a,b.a),dis(a.a,b.b)),min(dis(a.b,b.a),dis(a.b,b.b)));
	point res=project(a,b.a);
	if(on_line(a.a,a.b,res)==2) ans=min(ans,dis(res,b.a));
	res=project(a,b.b);
	if(on_line(a.a,a.b,res)==2) ans=min(ans,dis(res,b.b));
	res=project(b,a.a);
	if(on_line(b.a,b.b,res)==2) ans=min(ans,dis(res,a.a));
	res=project(b,a.b);
	if(on_line(b.a,b.b,res)==2) ans=min(ans,dis(res,a.b));
	return ans;
}
struct polygon{
	vector<point>p;
	void read(int n=-1)
	{
		if(n<0) scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			point a;
			a.read();
			p.push_back(a);
		}
	}
	double area(void)
	{
		double ans=0;
		for(int i=1;i<p.size();i++)
		ans+=cross3(p[0],p[i-1],p[i])/2;
		return abs(ans);
	}
	bool convex(void)
	{
		short int right=-1;
		for(int i=2;i<p.size();i++)
		if(right<0) right=cross3(p[i-2],p[i-1],p[i])>=0;
		else if(right!=(cross3(p[i-2],p[i-1],p[i])>=0)) return false;
		if(right!=(cross3(p[p.size()-2],p[p.size()-1],p[0])>=0)) return false;
		return true;
	}
	short int in_polygon(const point x)
	{
		Line l(x,x+point(inf,(double)inf*1.414213562373));
		make_rand(l.b.y);
		int cnt=0;
		for(int i=1;i<p.size();i++)
		{
			Line u(p[i-1],p[i]);
			if(u && l)
			{
				cnt++;
				if(abs(cross3(p[i-1],p[i],x))<eps && on_line(p[i-1],p[i],x)==2) return 1;
			}
		}
		Line u(p[p.size()-1],p[0]);
		if(u && l)
		{
			cnt++;
			if(abs(cross3(p[p.size()-1],p[0],x))<eps && on_line(p[p.size()-1],p[0],x)==2) return 1;
		}
		return cnt%2==0?0:2; 
	}
}p;
int main()
{
	int n;
	scanf("%d",&n);
	
	srand(n);
	p.read(n);
	int q;
	scanf("%d",&q);
	while(q--)
	{
		point x;
		x.read();
		printf("%d\n",p.in_polygon(x));
	}
	return 0;
}


```