#include <cmath>

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

typedef double D;
const D EPS = 1e-8;
const D INF = 1e10;
const D PI = M_PI;
int sign(D a, D b = 0.0) {
    if(a < b - EPS) return -1;
    if(a > b + EPS) return +1;
    return 0;
}

struct P {
    D x, y;
    P(D xs, D ys) : x(xs), y(ys) { }
    P() { }
};
P operator +(P a, P b) { return P(a.x + b.x, a.y + b.y); }
P operator -(P a, P b) { return P(a.x - b.x, a.y - b.y); }
P operator *(P p, D s) { return P(p.x * s, p.y * s); }
P vec(P from, P to) { return to - from; }

D inp(P a, P b) { return a.x*b.x + a.y*b.y; }
D outp(P a, P b) { return a.x*b.y - a.y*b.x; }
D norm(P p) { return inp(p, p); }
D abs(P p) { return sqrt(norm(p)); }
bool eq(P a, P b) { return abs(a - b) < EPS; }
D arg(P p) { return atan2(p.y, p.x); }
P rot90(P p) {
    return P(-p.y, p.x);
}
P rot(P p, D radian) {
    P q;
    q.x = cos(radian)*p.x - sin(radian)*p.y;
    q.y = sin(radian)*p.x + cos(radian)*p.y;
    return q;
}
struct L {
    P a, b;
    L(P as, P bs) : a(as), b(bs) { }
};
P projection(L l, P p) { // ??´???l???????????????p?????????
    P a = vec(l.a, l.b);
    P b = vec(l.a, p);
    D t = inp(b, a) / norm(a);
    return l.a + a * t;
}
P reflection(L l, P p) { // ??´???l???????????????p???????°?
    return p + vec(p, projection(l, p)) * 2;
}
int ccw(P a, P b, P c) {
    b = vec(a, b); c = vec(a, c);

    // a - b - c ????????????????????¨???
    if(sign(outp(b, c)) > 0) return +1; // ???????¨???????
    if(sign(outp(b, c)) < 0) return -1; // ????¨???????

    // a - b - c ?????´??????????????¶??¨???
    if(sign(inp(b, c)) < 0) return +2; // c - a - b
    if(norm(b) < norm(c))   return -2; // a - b - c
    return 0;                          // a - c - b
}
bool iSS(L s, L t) { // ????????????
    return ccw(s.a, s.b, t.a) * ccw(s.a, s.b, t.b) <= 0 &&
           ccw(t.a, t.b, s.a) * ccw(t.a, t.b, s.b) <= 0;
}
bool iSP(L s, P p) {
    return ccw(s.a, s.b, p) == 0;
}
D dSP(L s, P p) {
    P r = projection(s, p);
    if(iSP(s, r)) return abs(vec(p, r));
    return min(abs(vec(p, s.a)), abs(vec(p, s.b)));
}
D dSS(L s, L t) {
    if(iSS(s, t)) return 0;
    return min(min(dSP(s, t.a), dSP(s, t.b)),
               min(dSP(t, s.a), dSP(t, s.b)));
}
/* ?????????????????¨??????iSS(s,t)????¢???????????????¨ */
P cLL(L l, L m) {
    D d = outp(vec(m.a, m.b), vec(l.a, l.b));
    return l.a + vec(l.a, l.b) * outp(vec(m.a, m.b), vec(l.a, m.b)) * (1.0 / d);
}

typedef vector<P> G;
P at(G g, int i) { return g[i % g.size()]; }
D areaG(G g) {
    D res = 0.0;
    for(int i = 0; i < (int)g.size(); i++) {
        res += outp(at(g, i), at(g, i + 1));
    }
    return res / 2.0;
}
// ON = 0, IN = 1, OUT = -1
int containsGP(G g, P p) {
    int side = -1;
    for(int i = 0; i < (int)g.size(); i++) {
        if(ccw(at(g, i), at(g, i + 1), p) == 0) return 0;
        P a = vec(p, at(g, i));
        P b = vec(p, at(g, i + 1));
        if(a.y > b.y) swap(a, b);
        if(sign(a.y) <= 0 && sign(b.y) > 0 && sign(outp(a, b)) > 0) side *= -1;
    }
    return side;
}
struct C {
    P p; D r;
    C(P ps, D rs) : p(ps), r(rs) { }
    C() { }
};

int main() {
    int N; cin >> N;
    G g(N);
    for(int i = 0; i < N; i++) {
        cin >> g[i].x >> g[i].y;
    }
    int M; cin >> M;
    for(int i = 0; i < M; i++) {
        int x, y; cin >> x >> y;
        int res = containsGP(g, P(x, y));
        cout << res + 1 << endl;
    }
}
### 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
#include <cmath>

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

typedef double D;
const D EPS = 1e-8;
const D INF = 1e10;
const D PI = M_PI;
int sign(D a, D b = 0.0) {
    if(a < b - EPS) return -1;
    if(a > b + EPS) return +1;
    return 0;
}

struct P {
    D x, y;
    P(D xs, D ys) : x(xs), y(ys) { }
    P() { }
};
P operator +(P a, P b) { return P(a.x + b.x, a.y + b.y); }
P operator -(P a, P b) { return P(a.x - b.x, a.y - b.y); }
P operator *(P p, D s) { return P(p.x * s, p.y * s); }
P vec(P from, P to) { return to - from; }

D inp(P a, P b) { return a.x*b.x + a.y*b.y; }
D outp(P a, P b) { return a.x*b.y - a.y*b.x; }
D norm(P p) { return inp(p, p); }
D abs(P p) { return sqrt(norm(p)); }
bool eq(P a, P b) { return abs(a - b) < EPS; }
D arg(P p) { return atan2(p.y, p.x); }
P rot90(P p) {
    return P(-p.y, p.x);
}
P rot(P p, D radian) {
    P q;
    q.x = cos(radian)*p.x - sin(radian)*p.y;
    q.y = sin(radian)*p.x + cos(radian)*p.y;
    return q;
}
struct L {
    P a, b;
    L(P as, P bs) : a(as), b(bs) { }
};
P projection(L l, P p) { // ??´???l???????????????p?????????
    P a = vec(l.a, l.b);
    P b = vec(l.a, p);
    D t = inp(b, a) / norm(a);
    return l.a + a * t;
}
P reflection(L l, P p) { // ??´???l???????????????p???????°?
    return p + vec(p, projection(l, p)) * 2;
}
int ccw(P a, P b, P c) {
    b = vec(a, b); c = vec(a, c);

    // a - b - c ????????????????????¨???
    if(sign(outp(b, c)) > 0) return +1; // ???????¨???????
    if(sign(outp(b, c)) < 0) return -1; // ????¨???????

    // a - b - c ?????´??????????????¶??¨???
    if(sign(inp(b, c)) < 0) return +2; // c - a - b
    if(norm(b) < norm(c))   return -2; // a - b - c
    return 0;                          // a - c - b
}
bool iSS(L s, L t) { // ????????????
    return ccw(s.a, s.b, t.a) * ccw(s.a, s.b, t.b) <= 0 &&
           ccw(t.a, t.b, s.a) * ccw(t.a, t.b, s.b) <= 0;
}
bool iSP(L s, P p) {
    return ccw(s.a, s.b, p) == 0;
}
D dSP(L s, P p) {
    P r = projection(s, p);
    if(iSP(s, r)) return abs(vec(p, r));
    return min(abs(vec(p, s.a)), abs(vec(p, s.b)));
}
D dSS(L s, L t) {
    if(iSS(s, t)) return 0;
    return min(min(dSP(s, t.a), dSP(s, t.b)),
               min(dSP(t, s.a), dSP(t, s.b)));
}
/* ?????????????????¨??????iSS(s,t)????¢???????????????¨ */
P cLL(L l, L m) {
    D d = outp(vec(m.a, m.b), vec(l.a, l.b));
    return l.a + vec(l.a, l.b) * outp(vec(m.a, m.b), vec(l.a, m.b)) * (1.0 / d);
}

typedef vector<P> G;
P at(G g, int i) { return g[i % g.size()]; }
D areaG(G g) {
    D res = 0.0;
    for(int i = 0; i < (int)g.size(); i++) {
        res += outp(at(g, i), at(g, i + 1));
    }
    return res / 2.0;
}
// ON = 0, IN = 1, OUT = -1
int containsGP(G g, P p) {
    int side = -1;
    for(int i = 0; i < (int)g.size(); i++) {
        if(ccw(at(g, i), at(g, i + 1), p) == 0) return 0;
        P a = vec(p, at(g, i));
        P b = vec(p, at(g, i + 1));
        if(a.y > b.y) swap(a, b);
        if(sign(a.y) <= 0 && sign(b.y) > 0 && sign(outp(a, b)) > 0) side *= -1;
    }
    return side;
}
struct C {
    P p; D r;
    C(P ps, D rs) : p(ps), r(rs) { }
    C() { }
};

int main() {
    int N; cin >> N;
    G g(N);
    for(int i = 0; i < N; i++) {
        cin >> g[i].x >> g[i].y;
    }
    int M; cin >> M;
    for(int i = 0; i < M; i++) {
        int x, y; cin >> x >> y;
        int res = containsGP(g, P(x, y));
        cout << res + 1 << endl;
    }
}
```