/* Header {{{ */
#include <bits/stdc++.h>
using namespace std;

typedef long long readtype;
typedef long long var;
typedef long double let;

readtype read() {
  readtype a = 0, c = getchar(), s = 0;
  while (!isdigit(c)) s |= c == '-', c = getchar();
  while (isdigit(c)) a = a * 10 + c - 48, c = getchar();
  return s ? -a : a;
}

#ifdef LOCAL_LOGGER
#define logger(...) fprintf(stderr, __VA_ARGS__)
#define abortif(v, ...) if (v) {logger("Error in Line %d, Function '%s()'.\nInfo: ", __LINE__, __FUNCTION__); logger(__VA_ARGS__); exit(0);}
#else
#define logger(...);
#define abortif(v, ...);
#endif
/* }}} */

const let EPS = 1e-8;

int sign(let x) { return (x < -EPS) ? -1 : (x > EPS) ? 1 : 0; }

struct Point {
  let x, y;

  friend Point operator - (Point a, Point b) {
    return (Point) {a.x - b.x, a.y - b.y};
  }
  Point operator * (let k) { return (Point) {x * k, y * k}; }

  friend bool operator == (Point a, Point b) {
    return sign(a.x - b.x) == 0 && sign(a.y - b.y) == 0;
  }

  let dist() {
    return sqrt(x * x + y * y);
  }

  friend let Times(Point a, Point b) {
    return a.x * b.y - a.y * b.x;
  }

  Point Rotate(let sink, let cosk) {
    return (Point) {
      x * cosk - y * sink, x * sink + y * cosk
    };
  }

  Point Rotate(let k) {
    return Rotate(sin(k), cos(k));
  }
};

typedef Point Vec;

struct Segment {
  Point s, e;
  Vec v;
  Segment() {}
  Segment(Point a, Point b) {
    s = a, e = b, v = b - a;
  }
  Segment(Point a, Point b, Vec c) {
    s = a, e = b, v = c;
  }

  let CrossX() {
    let res = (e - v * (e.y / v.y)).x;
    return res;
  }

  friend bool InSegment(Segment s, Point p) {
    if (sign(Times(s.v, p - s.s)) == 0) {
      if (sign(p.x - min(s.s.x, s.e.x)) < 0) return false;
      if (sign(p.y - min(s.s.y, s.e.y)) < 0) return false;
      if (sign(p.x - max(s.s.x, s.e.x)) > 0) return false;
      if (sign(p.y - max(s.s.y, s.e.y)) > 0) return false;
      return true;
    }
    return false;
  }
};

struct Polygon {
  vector<Point> p;

  void Add(Point x) { p.push_back(x); }

  Point &operator [] (int k) { return p.at(k); }

  Polygon operator - (Vec k) {
    Polygon x;
    for (size_t i = 0; i < this->p.size(); ++i)
      x.Add(this->p.at(i) - k);
    return x;
  }

  Polygon Rotate(let sink, let cosk) {
    Polygon x;
    for (size_t i = 0; i < this->p.size(); ++i)
      x.Add(this->p.at(i).Rotate(sink, cosk));
    return x;
  }

  Polygon Rotate(let k) {
    return Rotate(sin(k), cos(k));
  }

  Polygon Rotate(Vec k) {
    let z = k.dist();
    return Rotate(k.y / z, k.x / z);
  }

  friend int CheckPIP(Polygon poly, Point p) {
    poly.Add(poly[0]);
    for (size_t i = 0; i < poly.p.size() - 1; ++i) {
      if (InSegment((Segment) {poly[i], poly[i + 1]}, p)) return 1;
    }

    Polygon x = poly - p;
    int have = 0;
    for (size_t i = 0; i < x.p.size() - 1; ++i) {
      if (sign(x[i].x) < 0 && sign(x[i + 1].x) < 0) continue;
      if (sign(x[i].y) > 0 && sign(x[i + 1].y) > 0) continue;
      if (sign(x[i].y) < 0 && sign(x[i + 1].y) < 0) continue;
      if (sign(((Segment) {x[i], x[i + 1]}).CrossX()) < 0) continue;
      have++;
    }
    if (have & 1) return 2;
    return 0;
  }

};

Point ReadPoint() {
  Point p;
  scanf("%Lf%LF", &p.x, &p.y);
  return p;
}

Polygon ReadPolygon() {
  Polygon poly;
  int g = read();
  for (int i = 1; i <= g; ++i)
    poly.Add(ReadPoint());
  return poly;
}

Polygon poly;

int main() {
// #ifndef ONLINE_JUDGE
//   freopen("CGL_3_C.in", "r", stdin);
//   freopen("CGL_3_C.out", "w", stdout);
// #endif
// #ifdef LOCAL_LOGGER
//   freopen("CGL_3_C.log", "w", stderr);
// #endif
  srand(time(0));
  let angle = ((let) rand() / RAND_MAX) * acos(-1.0);

  poly = ReadPolygon().Rotate(angle);

  int q = read();
  while (q--) {
    Point p = ReadPoint().Rotate(angle);
    printf("%d\n", CheckPIP(poly, p));
  }
  return 0;
}

/* ==== Makefile ==== {{{
CompileAndRun:
	make Compile
	make Run

Compile:
	g++ -o CGL_3_C CGL_3_C.cpp -g -Wall -DLOCAL_LOGGER

CompileUF:
	g++ -o CGL_3_C CGL_3_C.cpp -g -Wall -DLOCAL_LOGGER -fsanitize=undefined

Run:
	./CGL_3_C < CGL_3_C.in > CGL_3_C.out
==================
}}} */


### Prompt

Create a solution in CPP for 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
/* Header {{{ */
#include <bits/stdc++.h>
using namespace std;

typedef long long readtype;
typedef long long var;
typedef long double let;

readtype read() {
  readtype a = 0, c = getchar(), s = 0;
  while (!isdigit(c)) s |= c == '-', c = getchar();
  while (isdigit(c)) a = a * 10 + c - 48, c = getchar();
  return s ? -a : a;
}

#ifdef LOCAL_LOGGER
#define logger(...) fprintf(stderr, __VA_ARGS__)
#define abortif(v, ...) if (v) {logger("Error in Line %d, Function '%s()'.\nInfo: ", __LINE__, __FUNCTION__); logger(__VA_ARGS__); exit(0);}
#else
#define logger(...);
#define abortif(v, ...);
#endif
/* }}} */

const let EPS = 1e-8;

int sign(let x) { return (x < -EPS) ? -1 : (x > EPS) ? 1 : 0; }

struct Point {
  let x, y;

  friend Point operator - (Point a, Point b) {
    return (Point) {a.x - b.x, a.y - b.y};
  }
  Point operator * (let k) { return (Point) {x * k, y * k}; }

  friend bool operator == (Point a, Point b) {
    return sign(a.x - b.x) == 0 && sign(a.y - b.y) == 0;
  }

  let dist() {
    return sqrt(x * x + y * y);
  }

  friend let Times(Point a, Point b) {
    return a.x * b.y - a.y * b.x;
  }

  Point Rotate(let sink, let cosk) {
    return (Point) {
      x * cosk - y * sink, x * sink + y * cosk
    };
  }

  Point Rotate(let k) {
    return Rotate(sin(k), cos(k));
  }
};

typedef Point Vec;

struct Segment {
  Point s, e;
  Vec v;
  Segment() {}
  Segment(Point a, Point b) {
    s = a, e = b, v = b - a;
  }
  Segment(Point a, Point b, Vec c) {
    s = a, e = b, v = c;
  }

  let CrossX() {
    let res = (e - v * (e.y / v.y)).x;
    return res;
  }

  friend bool InSegment(Segment s, Point p) {
    if (sign(Times(s.v, p - s.s)) == 0) {
      if (sign(p.x - min(s.s.x, s.e.x)) < 0) return false;
      if (sign(p.y - min(s.s.y, s.e.y)) < 0) return false;
      if (sign(p.x - max(s.s.x, s.e.x)) > 0) return false;
      if (sign(p.y - max(s.s.y, s.e.y)) > 0) return false;
      return true;
    }
    return false;
  }
};

struct Polygon {
  vector<Point> p;

  void Add(Point x) { p.push_back(x); }

  Point &operator [] (int k) { return p.at(k); }

  Polygon operator - (Vec k) {
    Polygon x;
    for (size_t i = 0; i < this->p.size(); ++i)
      x.Add(this->p.at(i) - k);
    return x;
  }

  Polygon Rotate(let sink, let cosk) {
    Polygon x;
    for (size_t i = 0; i < this->p.size(); ++i)
      x.Add(this->p.at(i).Rotate(sink, cosk));
    return x;
  }

  Polygon Rotate(let k) {
    return Rotate(sin(k), cos(k));
  }

  Polygon Rotate(Vec k) {
    let z = k.dist();
    return Rotate(k.y / z, k.x / z);
  }

  friend int CheckPIP(Polygon poly, Point p) {
    poly.Add(poly[0]);
    for (size_t i = 0; i < poly.p.size() - 1; ++i) {
      if (InSegment((Segment) {poly[i], poly[i + 1]}, p)) return 1;
    }

    Polygon x = poly - p;
    int have = 0;
    for (size_t i = 0; i < x.p.size() - 1; ++i) {
      if (sign(x[i].x) < 0 && sign(x[i + 1].x) < 0) continue;
      if (sign(x[i].y) > 0 && sign(x[i + 1].y) > 0) continue;
      if (sign(x[i].y) < 0 && sign(x[i + 1].y) < 0) continue;
      if (sign(((Segment) {x[i], x[i + 1]}).CrossX()) < 0) continue;
      have++;
    }
    if (have & 1) return 2;
    return 0;
  }

};

Point ReadPoint() {
  Point p;
  scanf("%Lf%LF", &p.x, &p.y);
  return p;
}

Polygon ReadPolygon() {
  Polygon poly;
  int g = read();
  for (int i = 1; i <= g; ++i)
    poly.Add(ReadPoint());
  return poly;
}

Polygon poly;

int main() {
// #ifndef ONLINE_JUDGE
//   freopen("CGL_3_C.in", "r", stdin);
//   freopen("CGL_3_C.out", "w", stdout);
// #endif
// #ifdef LOCAL_LOGGER
//   freopen("CGL_3_C.log", "w", stderr);
// #endif
  srand(time(0));
  let angle = ((let) rand() / RAND_MAX) * acos(-1.0);

  poly = ReadPolygon().Rotate(angle);

  int q = read();
  while (q--) {
    Point p = ReadPoint().Rotate(angle);
    printf("%d\n", CheckPIP(poly, p));
  }
  return 0;
}

/* ==== Makefile ==== {{{
CompileAndRun:
	make Compile
	make Run

Compile:
	g++ -o CGL_3_C CGL_3_C.cpp -g -Wall -DLOCAL_LOGGER

CompileUF:
	g++ -o CGL_3_C CGL_3_C.cpp -g -Wall -DLOCAL_LOGGER -fsanitize=undefined

Run:
	./CGL_3_C < CGL_3_C.in > CGL_3_C.out
==================
}}} */


```