#define _USE_MATH_DEFINES
#include<iostream>
#include<algorithm>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<deque>
#include<queue>
#include<map>
#include<set>
#define ll long long
#define str string
#define ld long double
#define vec vector
#define vll vec<ll>
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define rrep(i,b,a) for(ll i=b;i>=a;i--)
#define ALL(a) a.begin(),a.end()
#define rALL(a) a.rbegin(),a.rend()
#define kai "\n"
#define yuque priority_queue
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define mie min_element
#define mae max_element
#define tos to_string
#define sep setprecision
#define lob lower_bound
#define upb upper_bound
#define nep next_permutation
#define MOD 1000000007ll
#define MIN (1e-10)
#define equal(a,b) (abs((a)-(b))<MIN)
#define v2 ten
#define chokusen senbun
#define tenten senbun
#define takaku vec<ten>
#define kakudo(a) atan2((a).y,(a).x)
#define beku(r,t) (v2){(r)*cos(t),(r)*sin(t)}
using namespace std;
void solve();
int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout<<fixed;
	solve();
}
struct pea{
	ll f,s;
	bool operator<(const pea &p)const{
		return f!=p.f?f<p.f:s<p.s;
	};
};
struct tri{
	ll f,s,t;
	bool operator<(const tri &p)const{return f<p.f;};
};
class ten{
public:
	ld x,y;
	ten operator+(ten p){return{x+p.x,y+p.y};}
	ten operator-(ten p){return{x-p.x,y-p.y};}
	ten operator*(ld k){return{k*x,k*y};}
	ten operator/(ld k){return{x/k,y/k};}
	ld abs(){return sqrt(abs2());}
	ld abs2(){return x*x+y*y;};
	bool operator<(const ten &p)const{return x!=p.x?x<p.x:y<p.y;};
	bool operator==(const ten &p)const{return (-MIN<x-p.x)&&(x-p.x<MIN)&&(-MIN<y-p.y)&&(y-p.y<MIN);};
	ld naiseki(v2 b){return x*b.x+y*b.y;}
	ld gaiseki(v2 b){return x*b.y-y*b.x;}
};
struct senbun{ten p1,p2;};
struct en{ten o;ld r;};
ten shaei(ten p,chokusen l){
	v2 a=l.p2-l.p1;
	return l.p1+a*a.naiseki(p-l.p1)/a.abs2();
}
ten hansha(ten p,chokusen l){return shaei(p,l)*2-p;}
ld tenchoku(ten p,chokusen l){
	v2 a=l.p2-l.p1;
	return abs(a.gaiseki(p-l.p1))/a.abs();
}
ld tensen(ten p,senbun s){
	if((p-s.p1).naiseki(s.p2-s.p1)<0)return (p-s.p1).abs();
	if((p-s.p2).naiseki(s.p1-s.p2)<0)return (p-s.p2).abs();
	return tenchoku(p,s);
}
ll ccw(ten p0,ten p1,ten p2){
	v2 a=p1-p0,b=p2-p0;
	if(a.gaiseki(b)>MIN)return -1;//012反時計回り
	if(a.gaiseki(b)<-MIN)return 1;//012時計回り
	if(a.naiseki(b)<-MIN)return -2;//102
	if(a.abs2()<b.abs2())return 2;//012
	return 0;//021
}
bool majiwaru(senbun s,senbun t){return ccw(s.p1,s.p2,t.p1)*ccw(s.p1,s.p2,t.p2)<=0&&ccw(t.p1,t.p2,s.p1)*ccw(t.p1,t.p2,s.p2)<=0;}
ld sensen(senbun s,senbun t){
	if(majiwaru(s,t))return 0;
	return min({tensen(s.p1,t),tensen(s.p2,t),tensen(t.p1,s),tensen(t.p2,s)});
}
ten koten(senbun s,senbun t){
	v2 a=t.p2-t.p1;
	ld d1=abs(a.gaiseki(s.p1-t.p1));
	ld d2=abs(a.gaiseki(s.p2-t.p1));
	return s.p1+(s.p2-s.p1)*d1/(d1+d2);
}
tenten koten(en c,chokusen l){
	ten h=shaei(c.o,l);
	ld k=sqrt(c.r*c.r-(h-c.o).abs2());
	v2 a=(l.p1-l.p2)/(l.p1-l.p2).abs();
	return {h+a*k,h-a*k};
}
tenten koten(en c1,en c2){
	ld d=(c2.o-c1.o).abs();
	ld s=acos((c1.r*c1.r+d*d-c2.r*c2.r)/(2*c1.r*d));
	ld t=kakudo(c2.o-c1.o);
	return {c1.o+beku(c1.r,t+s),c1.o+beku(c1.r,t-s)};
}
ll uchi(ten p,takaku &g){
	//2:IN,1:ON,0:OUT
	ll n=g.size();
	v2 a,b;
	bool x=false;
	rep(i,0,n){
		a=g[i]-p;b=g[(i+1)%n]-p;
		if(abs(a.gaiseki(b))<MIN&&a.naiseki(b)<MIN)return 1;
		if(a.y>b.y)swap(a,b);
		if(a.y<MIN&&MIN<b.y&&a.gaiseki(b)>MIN)x=!x;
	}
	return x?2:0;
}
//凸包
takaku andrew(takaku s){
	takaku u,l;
	
}
void solve(){
	ll n;cin>>n;
	takaku g(n);
	rep(i,0,n)cin>>g[i].x>>g[i].y;
	cin>>n;
	ten p;
	rep(i,0,n){
		cin>>p.x>>p.y;
		cout<<uchi(p,g)<<kai;
	}
}

### Prompt

In Cpp, your task is to solve 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
#define _USE_MATH_DEFINES
#include<iostream>
#include<algorithm>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<deque>
#include<queue>
#include<map>
#include<set>
#define ll long long
#define str string
#define ld long double
#define vec vector
#define vll vec<ll>
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define rrep(i,b,a) for(ll i=b;i>=a;i--)
#define ALL(a) a.begin(),a.end()
#define rALL(a) a.rbegin(),a.rend()
#define kai "\n"
#define yuque priority_queue
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define mie min_element
#define mae max_element
#define tos to_string
#define sep setprecision
#define lob lower_bound
#define upb upper_bound
#define nep next_permutation
#define MOD 1000000007ll
#define MIN (1e-10)
#define equal(a,b) (abs((a)-(b))<MIN)
#define v2 ten
#define chokusen senbun
#define tenten senbun
#define takaku vec<ten>
#define kakudo(a) atan2((a).y,(a).x)
#define beku(r,t) (v2){(r)*cos(t),(r)*sin(t)}
using namespace std;
void solve();
int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout<<fixed;
	solve();
}
struct pea{
	ll f,s;
	bool operator<(const pea &p)const{
		return f!=p.f?f<p.f:s<p.s;
	};
};
struct tri{
	ll f,s,t;
	bool operator<(const tri &p)const{return f<p.f;};
};
class ten{
public:
	ld x,y;
	ten operator+(ten p){return{x+p.x,y+p.y};}
	ten operator-(ten p){return{x-p.x,y-p.y};}
	ten operator*(ld k){return{k*x,k*y};}
	ten operator/(ld k){return{x/k,y/k};}
	ld abs(){return sqrt(abs2());}
	ld abs2(){return x*x+y*y;};
	bool operator<(const ten &p)const{return x!=p.x?x<p.x:y<p.y;};
	bool operator==(const ten &p)const{return (-MIN<x-p.x)&&(x-p.x<MIN)&&(-MIN<y-p.y)&&(y-p.y<MIN);};
	ld naiseki(v2 b){return x*b.x+y*b.y;}
	ld gaiseki(v2 b){return x*b.y-y*b.x;}
};
struct senbun{ten p1,p2;};
struct en{ten o;ld r;};
ten shaei(ten p,chokusen l){
	v2 a=l.p2-l.p1;
	return l.p1+a*a.naiseki(p-l.p1)/a.abs2();
}
ten hansha(ten p,chokusen l){return shaei(p,l)*2-p;}
ld tenchoku(ten p,chokusen l){
	v2 a=l.p2-l.p1;
	return abs(a.gaiseki(p-l.p1))/a.abs();
}
ld tensen(ten p,senbun s){
	if((p-s.p1).naiseki(s.p2-s.p1)<0)return (p-s.p1).abs();
	if((p-s.p2).naiseki(s.p1-s.p2)<0)return (p-s.p2).abs();
	return tenchoku(p,s);
}
ll ccw(ten p0,ten p1,ten p2){
	v2 a=p1-p0,b=p2-p0;
	if(a.gaiseki(b)>MIN)return -1;//012反時計回り
	if(a.gaiseki(b)<-MIN)return 1;//012時計回り
	if(a.naiseki(b)<-MIN)return -2;//102
	if(a.abs2()<b.abs2())return 2;//012
	return 0;//021
}
bool majiwaru(senbun s,senbun t){return ccw(s.p1,s.p2,t.p1)*ccw(s.p1,s.p2,t.p2)<=0&&ccw(t.p1,t.p2,s.p1)*ccw(t.p1,t.p2,s.p2)<=0;}
ld sensen(senbun s,senbun t){
	if(majiwaru(s,t))return 0;
	return min({tensen(s.p1,t),tensen(s.p2,t),tensen(t.p1,s),tensen(t.p2,s)});
}
ten koten(senbun s,senbun t){
	v2 a=t.p2-t.p1;
	ld d1=abs(a.gaiseki(s.p1-t.p1));
	ld d2=abs(a.gaiseki(s.p2-t.p1));
	return s.p1+(s.p2-s.p1)*d1/(d1+d2);
}
tenten koten(en c,chokusen l){
	ten h=shaei(c.o,l);
	ld k=sqrt(c.r*c.r-(h-c.o).abs2());
	v2 a=(l.p1-l.p2)/(l.p1-l.p2).abs();
	return {h+a*k,h-a*k};
}
tenten koten(en c1,en c2){
	ld d=(c2.o-c1.o).abs();
	ld s=acos((c1.r*c1.r+d*d-c2.r*c2.r)/(2*c1.r*d));
	ld t=kakudo(c2.o-c1.o);
	return {c1.o+beku(c1.r,t+s),c1.o+beku(c1.r,t-s)};
}
ll uchi(ten p,takaku &g){
	//2:IN,1:ON,0:OUT
	ll n=g.size();
	v2 a,b;
	bool x=false;
	rep(i,0,n){
		a=g[i]-p;b=g[(i+1)%n]-p;
		if(abs(a.gaiseki(b))<MIN&&a.naiseki(b)<MIN)return 1;
		if(a.y>b.y)swap(a,b);
		if(a.y<MIN&&MIN<b.y&&a.gaiseki(b)>MIN)x=!x;
	}
	return x?2:0;
}
//凸包
takaku andrew(takaku s){
	takaku u,l;
	
}
void solve(){
	ll n;cin>>n;
	takaku g(n);
	rep(i,0,n)cin>>g[i].x>>g[i].y;
	cin>>n;
	ten p;
	rep(i,0,n){
		cin>>p.x>>p.y;
		cout<<uchi(p,g)<<kai;
	}
}

```