Problem: Petya has a polygon consisting of n vertices. All sides of the Petya's polygon are parallel to the coordinate axes, and each two adjacent sides of the Petya's polygon are perpendicular. It is guaranteed that the polygon is simple, that is, it doesn't have self-intersections and self-touches. All internal area of the polygon (borders are not included) was painted in black color by Petya.

Also, Petya has a rectangular window, defined by its coordinates, through which he looks at the polygon. A rectangular window can not be moved. The sides of the rectangular window are parallel to the coordinate axes.

<image> Blue color represents the border of a polygon, red color is the Petya's window. The answer in this case is 2.

Determine the number of black connected areas of Petya's polygon, which can be seen through the rectangular window.

Input

The first line contain four integers x_1, y_1, x_2, y_2 (x_1 < x_2, y_2 < y_1) — the coordinates of top-left and bottom-right corners of the rectangular window. 

The second line contains a single integer n (4 ≤ n ≤ 15 000) — the number of vertices in Petya's polygon.

Each of the following n lines contains two integers — the coordinates of vertices of the Petya's polygon in counterclockwise order. Guaranteed, that the given polygon satisfies the conditions described in the statement.

All coordinates of the rectangular window and all coordinates of the vertices of the polygon are non-negative and do not exceed 15 000.

Output

Print the number of black connected areas of Petya's polygon, which can be seen through the rectangular window.

Example

Input

5 7 16 3
16
0 0
18 0
18 6
16 6
16 1
10 1
10 4
7 4
7 2
2 2
2 6
12 6
12 12
10 12
10 8
0 8


Output

2

Note

The example corresponds to the picture above.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 30005;
inline int sgn(int x) {
  if (x < 0)
    return -1;
  else if (x > 0)
    return 1;
  else
    return 0;
}
struct Point {
  int x, y;
  Point() {}
  Point(int x, int y) : x(x), y(y) {}
  bool operator<(const Point& rhs) const {
    if (x != rhs.x)
      return x < rhs.x;
    else
      return y < rhs.y;
  }
  bool operator==(const Point& rhs) const { return x == rhs.x && y == rhs.y; }
};
Point operator+(Point a, Point b) { return Point(a.x + b.x, a.y + b.y); }
Point operator-(Point a, Point b) { return Point(a.x - b.x, a.y - b.y); }
int dot(Point a, Point b) { return a.x * b.x + a.y * b.y; }
int cross(Point a, Point b) { return a.x * b.y - a.y * b.x; }
struct Segment {
  Point s, e;
  Segment() {}
  Segment(Point s, Point e) : s(s), e(e) {}
};
bool Point_on_Segment(Point p, Segment seg) {
  Point u = p - seg.s, v = p - seg.e;
  if (sgn(cross(u, v)) != 0) return false;
  return sgn(dot(u, v)) <= 0;
}
bool Segment_intersect(Segment a, Segment b, Point& res) {
  if (sgn(min(a.s.x, a.e.x) - max(b.s.x, b.e.x)) > 0 ||
      sgn(max(a.s.x, a.e.x) - min(b.s.x, b.e.x)) < 0 ||
      sgn(min(a.s.y, a.e.y) - max(b.s.y, b.e.y)) > 0 ||
      sgn(max(a.s.y, a.e.y) - min(b.s.y, b.e.y)) < 0)
    return false;
  if (cross(a.e - a.s, b.e - b.s) == 0) return false;
  if (a.s.x == a.e.x)
    res = Point(a.s.x, b.s.y);
  else
    res = Point(b.s.x, a.s.y);
  return true;
}
bool Point_on_Polygon(Point p, vector<Point>& poly) {
  int n = poly.size();
  for (int i = 0; i < n; i++)
    if (Point_on_Segment(p, Segment(poly[i], poly[(i + 1) % n]))) return true;
  return false;
}
bool Point_in_Polygon(Point p, vector<Point>& poly) {
  int cnt = 0;
  int n = poly.size();
  for (int i = 0; i < n; i++) {
    if (Point_on_Segment(p, Segment(poly[i], poly[(i + 1) % n]))) return false;
    int k = sgn(cross(poly[(i + 1) % n] - poly[i], p - poly[i]));
    int d1 = sgn(poly[i].y - p.y), d2 = sgn(poly[(i + 1) % n].y - p.y);
    if (k > 0 && d1 <= 0 && d2 > 0) cnt++;
    if (k < 0 && d2 <= 0 && d1 > 0) cnt--;
  }
  if (cnt != 0)
    return true;
  else
    return false;
}
bool Segment_intersect_Polygon(Segment seg, vector<Point>& poly, Segment& res) {
  int n = poly.size();
  vector<Point> v;
  for (int i = 0; i < n; i++) {
    if (cross(seg.e - seg.s, poly[(i + 1) % n] - poly[i]) == 0) continue;
    if (Point_on_Segment(poly[i], seg)) continue;
    Point p;
    if (Segment_intersect(seg, Segment(poly[i], poly[(i + 1) % n]), p)) {
      v.push_back(p);
    }
  }
  bool s = Point_in_Polygon(seg.s, poly), e = Point_in_Polygon(seg.e, poly);
  if (!s && !e && v.size() < 2) return false;
  if (s && e)
    res.s = seg.s, res.e = seg.e;
  else if (s)
    res.s = seg.s, res.e = v[0];
  else if (e)
    res.s = v[0], res.e = seg.e;
  else {
    assert(v.size() == 2);
    if (dot(seg.e - seg.s, v[1] - v[0]) < 0) swap(v[0], v[1]);
    res.s = v[0], res.e = v[1];
  }
  return true;
}
bool Polygon_in_Polygon(vector<Point>& a, vector<Point>& b) {
  for (auto& i : a)
    if (!Point_in_Polygon(i, b) && !Point_on_Polygon(i, b)) return false;
  return true;
}
struct Edge {
  int to;
  bool value, vis;
  Edge* next;
} * edges[MAXN], pool[MAXN * 2], *alloc = pool;
Edge* new_Edge(int from, int to, bool value) {
  Edge* ret = alloc++;
  ret->to = to;
  ret->value = value;
  ret->vis = false;
  ret->next = edges[from];
  return ret;
}
void add_edge(int from, int to) {
  edges[from] = new_Edge(from, to, true);
  edges[to] = new_Edge(to, from, false);
}
int n, ans;
vector<Point> rec, poly;
vector<Point> v;
map<Point, int> idx;
bool instk[MAXN];
void add_node(Point p) {
  if (idx.find(p) == idx.end()) {
    idx[p] = v.size();
    v.push_back(p);
  }
}
void dfs(int x, int y, bool flag) {
  if (instk[x]) {
    if (flag) ans++;
    return;
  }
  instk[x] = true;
  Edge* e = NULL;
  for (auto i = edges[x]; i; i = i->next)
    if (!i->vis && i->to != y) {
      if (e == NULL || cross(v[x] - v[y], v[i->to] - v[x]) >
                           cross(v[x] - v[y], v[e->to] - v[x]))
        e = i;
    }
  if (e) {
    e->vis = true;
    dfs(e->to, x, flag && e->value);
  }
  instk[x] = false;
}
int main() {
  int x1, y1, x2, y2;
  scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
  x1 *= 2, y1 *= 2, x2 *= 2, y2 *= 2;
  rec.emplace_back(x1, y1);
  rec.emplace_back(x2, y1);
  rec.emplace_back(x2, y2);
  rec.emplace_back(x1, y2);
  scanf("%d", &n);
  bool inner = true;
  for (int i = 0; i < n; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    x *= 2, y *= 2;
    if (x < x1 || x > x2 || y < y2 || y > y1) inner = false;
    poly.emplace_back(x, y);
  }
  if (inner) {
    printf("1\n");
    return 0;
  }
  for (int i = 0; i < n; i++) {
    Segment seg;
    if (Segment_intersect_Polygon(Segment(poly[i], poly[(i + 1) % n]), rec,
                                  seg)) {
      add_node(seg.s);
      add_node(seg.e);
      add_edge(idx[seg.s], idx[seg.e]);
    }
  }
  if (v.empty()) {
    if (Point_in_Polygon(Point((x1 + x2) / 2, (y1 + y2) / 2), poly))
      printf("1\n");
    else
      printf("0\n");
    return 0;
  }
  for (auto& i : rec) add_node(i);
  for (int i = 0; i < 4; i++) {
    vector<Point> e;
    Segment seg = Segment(rec[i], rec[(i + 1) % 4]);
    for (auto& j : v)
      if (Point_on_Segment(j, seg)) e.push_back(j);
    Point o = rec[(i + 2) % 4];
    sort(e.begin(), e.end(), [&o](const Point& a, const Point& b) -> bool {
      return cross(a - o, b - o) > 0;
    });
    for (int j = 1; j < (int)e.size(); j++) add_edge(idx[e[j - 1]], idx[e[j]]);
  }
  for (int i = 0; i < (int)v.size(); i++)
    for (auto j = edges[i]; j; j = j->next)
      if (!j->vis) {
        instk[i] = true;
        j->vis = true;
        dfs(j->to, i, j->value);
        instk[i] = false;
      }
  printf("%d\n", ans);
  return 0;
}