Problem: Anfisa the monkey got disappointed in word processors as they aren't good enough at reflecting all the range of her emotions, that's why she decided to switch to graphics editors. Having opened the BerPaint, she saw a white rectangle W × H in size which can be painted on. First Anfisa learnt to navigate the drawing tool which is used to paint segments and quickly painted on that rectangle a certain number of black-colored segments. The resulting picture didn't seem bright enough to Anfisa, that's why she turned her attention to the "fill" tool which is used to find a point on the rectangle to paint and choose a color, after which all the area which is the same color as the point it contains, is completely painted the chosen color. Having applied the fill several times, Anfisa expressed her emotions completely and stopped painting. Your task is by the information on the painted segments and applied fills to find out for every color the total area of the areas painted this color after all the fills.

Input

The first input line has two integers W and H (3 ≤ W, H ≤ 104) — the sizes of the initially white rectangular painting area. The second line contains integer n — the number of black segments (0 ≤ n ≤ 100). On the next n lines are described the segments themselves, each of which is given by coordinates of their endpoints x1, y1, x2, y2 (0 < x1, x2 < W, 0 < y1, y2 < H). All segments have non-zero length. The next line contains preset number of fills m (0 ≤ m ≤ 100). Each of the following m lines defines the fill operation in the form of "x y color", where (x, y) are the coordinates of the chosen point (0 < x < W, 0 < y < H), and color — a line of lowercase Latin letters from 1 to 15 symbols in length, determining the color. All coordinates given in the input are integers. Initially the rectangle is "white" in color, whereas the segments are drawn "black" in color.

Output

For every color present in the final picture print on the single line the name of the color and the total area of areas painted that color with an accuracy of 10 - 6. Print the colors in any order. 

Examples

Input

4 5
6
1 1 1 3
1 3 3 3
3 3 3 1
3 1 1 1
1 3 3 1
1 1 3 3
2
2 1 red
2 2 blue


Output

blue 0.00000000
white 20.00000000


Input

5 5
5
1 1 2 2
2 2 4 2
4 2 4 4
4 4 2 4
2 4 2 2
2
3 3 black
3 3 green


Output

green 4.00000000
white 21.00000000


Input

7 4
9
1 2 2 3
2 3 3 2
3 2 2 1
2 1 1 2
3 2 4 2
4 2 5 3
5 3 6 2
6 2 5 1
5 1 4 2
2
2 2 black
2 2 red


Output

red 2.00000000
white 26.00000000

Note

Initially the black segments painted by Anfisa can also be painted a color if any of the chosen points lays on the segment. The segments have areas equal to 0. That is why if in the final picture only parts of segments is painted some color, then the area, painted the color is equal to 0.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
const long double scale = 1000000000;
struct point {
  long double x, y;
  point() : x(0.0), y(0.0) {}
  point(const long double x, const long double y) : x(x), y(y) {}
};
struct segment {
  point a, b;
  int o;
};
struct triangle {
  int a, b, c, o, l0, l1, l2;
};
struct line {
  int a, b, o, next_a, next_b, t0, t1;
  line() : a(0), b(0), o(-1), next_a(-1), next_b(-1), t0(-1), t1(-1) {}
  line(const int a, const int b, const int o)
      : a(a), b(b), o(o), next_a(-1), next_b(-1), t0(-1), t1(-1) {}
};
static bool operator==(const point &a, const point &b) {
  return a.x == b.x && a.y == b.y;
}
static bool operator!=(const point &a, const point &b) {
  return a.x != b.x || a.y != b.y;
}
static bool operator<(const point &a, const point &b) {
  return a.y < b.y ? true : a.y > b.y ? false : a.x < b.x;
}
static point operator-(const point &a, const point &b) {
  return {a.x - b.x, a.y - b.y};
}
static point operator+(const point &a, const point &b) {
  return {a.x + b.x, a.y + b.y};
}
static point operator*(const long double s, const point &q) {
  return {static_cast<long double>(std::round(s * q.x)),
          static_cast<long double>(std::round(s * q.y))};
}
static long double dot(const point &a, const point &b) {
  return a.x * b.x + a.y * b.y;
}
static long double distance(const point &a, const point &b) {
  return std::sqrt(dot(a - b, a - b));
}
static bool segment_intersection(const segment &u, const segment &v, point *r) {
  const long double a = u.b.x - u.a.x, b = v.a.x - v.b.x;
  const long double c = u.b.y - u.a.y, d = v.a.y - v.b.y;
  const long double p = v.a.x - u.a.x, q = v.a.y - u.a.y;
  const long double det = a * d - b * c;
  const long double s = d * p + -b * q;
  const long double t = -c * p + a * q;
  if (det < 0   ? s <= 0 && det <= s && t <= 0 && det <= t
      : det > 0 ? 0 <= s && s <= det && 0 <= t && t <= det
                : false) {
    const long double m =
        static_cast<long double>(s) / static_cast<long double>(det);
    if (r != nullptr) *r = u.a + m * (u.b - u.a);
    return true;
  }
  return false;
}
static bool segment_point_intersection(const segment &l, const point &q) {
  const point a = l.a, b = l.b - a;
  return b.y * (q.x - a.x) != b.x * (q.y - a.y) ? false
         : b.x == 0 && b.y == 0                 ? l.a.x == q.x && l.a.y == q.y
         : b.x < 0 && q.x - a.x > 0             ? false
         : b.x > 0 && q.x - a.x < 0             ? false
         : b.x < 0 && b.x > q.x - a.x           ? false
         : b.x > 0 && b.x < q.x - a.x           ? false
         : b.y < 0 && q.y - a.y > 0             ? false
         : b.y > 0 && q.y - a.y < 0             ? false
         : b.y < 0 && b.y > q.y - a.y           ? false
         : b.y > 0 && b.y < q.y - a.y           ? false
                                                : true;
}
static bool triangle_point_intersection(const std::vector<point> &w,
                                        const triangle &u, const point &v) {
  const long double a = w[u.a].x - w[u.b].x, b = w[u.c].x - w[u.b].x;
  const long double c = w[u.a].y - w[u.b].y, d = w[u.c].y - w[u.b].y;
  const long double p = v.x - w[u.b].x, q = v.y - w[u.b].y;
  const long double det = a * d - b * c;
  const long double s = d * p + -b * q;
  const long double t = -c * p + a * q;
  return det < 0   ? s <= 0 && det <= s && t <= 0 && det <= t && det <= s + t
         : det > 0 ? 0 <= s && s <= det && 0 <= t && t <= det && s + t <= det
                   : false;
}
static std::vector<segment> cut_segments(const std::vector<segment> &s) {
  std::vector<std::set<point>> m(s.size());
  for (int i = 0; i < s.size(); i++)
    for (int j = i + 1; j < s.size(); j++) {
      point q;
      if (segment_intersection(s[i], s[j], &q)) {
        m[i].insert(q);
        m[j].insert(q);
      }
      if (segment_point_intersection(s[i], s[j].a)) m[i].insert(s[j].a);
      if (segment_point_intersection(s[i], s[j].b)) m[i].insert(s[j].b);
      if (segment_point_intersection(s[j], s[i].a)) m[j].insert(s[i].a);
      if (segment_point_intersection(s[j], s[i].b)) m[j].insert(s[i].b);
    }
  std::vector<segment> t;
  for (int i = 0; i < m.size(); i++) {
    m[i].insert(s[i].a);
    m[i].insert(s[i].b);
    std::vector<point> c(m[i].begin(), m[i].end());
    std::sort(c.begin(), c.end(), [&](const point &a, const point &b) {
      return distance(s[i].a, a) < distance(s[i].a, b);
    });
    for (int j = 1; j < c.size(); j++) t.push_back({c[j - 1], c[j], s[i].o});
  }
  return t;
}
static int color_index(std::map<std::string, int> &c, const std::string &o) {
  const std::map<std::string, int>::const_iterator i = c.find(o);
  return i != c.end() ? i->second : (c[o] = c.size());
}
static std::string color_name(const std::map<std::string, int> &c,
                              const int o) {
  for (const std::pair<std::string, int> &i : c)
    if (i.second == o) return i.first;
  return "";
}
static int point_index(std::map<point, int> &m, std::vector<point> &p,
                       const point &q) {
  const std::map<point, int>::const_iterator i = m.find(q);
  return i != m.end() ? i->second : (p.push_back(q), m[q] = p.size() - 1);
}
static int insert_edge(std::vector<line> &l, std::unordered_map<int, int> &e,
                       line k) {
  std::unordered_map<int, int>::iterator i = e.find(k.a), j = e.find(k.b);
  k.next_a = (i == e.end() ? -1 : i->second);
  k.next_b = (j == e.end() ? -1 : j->second);
  const int n = l.size();
  e[k.a] = e[k.b] = n;
  l.push_back(k);
  return n;
}
static void segments_to_lines(const std::vector<segment> &s,
                              std::vector<point> &p, std::vector<line> &l,
                              std::unordered_map<int, int> &e) {
  std::map<point, int> m;
  std::set<std::pair<int, int>> w;
  for (const point &i : p) {
    const int j = m.size();
    m[i] = j;
  }
  for (const segment &i : s) {
    const int a = point_index(m, p, i.a);
    const int b = point_index(m, p, i.b);
    const std::pair<int, int> h(a < b ? std::pair<int, int>({a, b})
                                      : std::pair<int, int>({b, a}));
    if (a != b && w.find(h) == w.end()) {
      insert_edge(l, e, line(a, b, i.o));
      w.insert(h);
    }
  }
}
static bool overlapping_segment(const std::vector<segment> &s,
                                const std::vector<point> &p, const int a,
                                const int b) {
  point q;
  for (const segment &i : s) {
    if (std::max(i.a.x, i.b.x) < std::min(p[a].x, p[b].x) ||
        std::max(i.a.y, i.b.y) < std::min(p[a].y, p[b].y) ||
        std::min(i.a.x, i.b.x) > std::max(p[a].x, p[b].x) ||
        std::min(i.a.y, i.b.y) > std::max(p[a].y, p[b].y))
      continue;
    if (segment_intersection({i.a, i.b}, {p[a], p[b]}, &q) &&
        distance(q, i.a) > scale && distance(q, i.b) > scale &&
        distance(q, p[a]) > scale && distance(q, p[b]) > scale)
      return true;
  }
  return false;
}
static bool overlapping_line(const std::vector<point> &p,
                             const std::vector<line> &l, const int a,
                             const int b) {
  for (int k = l.size() - 1; k >= 0; k--) {
    const line &i = l[k];
    if (std::max(p[i.a].x, p[i.b].x) < std::min(p[a].x, p[b].x) ||
        std::max(p[i.a].y, p[i.b].y) < std::min(p[a].y, p[b].y) ||
        std::min(p[i.a].x, p[i.b].x) > std::max(p[a].x, p[b].x) ||
        std::min(p[i.a].y, p[i.b].y) > std::max(p[a].y, p[b].y))
      continue;
    if ((i.a == a && i.b == b) || (i.a == b && i.b == a)) return true;
    if (i.a != a && i.a != b &&
        segment_point_intersection({p[a], p[b]}, p[i.a]))
      return true;
    if (i.b != a && i.b != b &&
        segment_point_intersection({p[a], p[b]}, p[i.b]))
      return true;
    point q;
    if (segment_intersection({p[i.a], p[i.b]}, {p[a], p[b]}, &q) &&
        ((q != p[a] && q != p[b]) || (q != p[i.a] && q != p[i.b])))
      return true;
  }
  return false;
}
static void iterate_lines(const int q, const std::vector<line> &l,
                          const std::unordered_map<int, int> &e,
                          std::function<void(const int i)> cb) {
  const std::unordered_map<int, int>::const_iterator i = e.find(q);
  for (int j = (i == e.end() ? -1 : i->second); j != -1;
       j = (l[j].a == q ? l[j].next_a : l[j].next_b))
    cb(j);
}
static int point_order(const int q, const std::vector<line> &l,
                       const std::unordered_map<int, int> &e) {
  int n = 0;
  iterate_lines(q, l, e, [&n](const int i) { n++; });
  return n;
}
static void iterate_triangles(
    const int q, const std::vector<point> &p, const std::vector<line> &l,
    const std::unordered_map<int, int> &e,
    const std::map<std::pair<int, int>, int> &w,
    std::function<void(const int a, const int b, const int c, const int i,
                       const int j, const int k)>
        cb) {
  const int n = point_order(q, l, e);
  int h = 0, v[n];
  iterate_lines(q, l, e, [&](const int i) { v[h++] = i; });
  std::sort(&v[0], &v[n], [&](const int i, const int j) {
    const point u = p[(l[i].a == q ? l[i].b : l[i].a)] - p[q];
    const point v = p[(l[j].a == q ? l[j].b : l[j].a)] - p[q];
    return std::atan2(u.x, u.y) < std::atan2(v.x, v.y);
  });
  for (h = 0; h < n; h++) {
    const int i = v[h], j = v[(h + 1) % n];
    const int a = q;
    const int b = (l[i].a == a ? l[i].b : l[i].a);
    const int c = (l[j].a == a ? l[j].b : l[j].a);
    const std::map<std::pair<int, int>, int>::const_iterator it =
        w.find({b, c});
    cb(a, b, c, i, j, (it != w.end() ? it->second : -1));
  }
}
static bool try_insert_edge(const std::vector<segment> &s,
                            const std::vector<point> &p, std::vector<line> &l,
                            std::unordered_map<int, int> &e,
                            std::map<std::pair<int, int>, int> &w, const int a,
                            const int b) {
  if (overlapping_segment(s, p, a, b)) return false;
  if (overlapping_line(p, l, a, b)) return false;
  w[{a, b}] = w[{b, a}] = insert_edge(l, e, line(a, b, -1));
  return true;
}
static void tesselate(std::vector<triangle> &t, const int o,
                      const std::vector<segment> &s,
                      const std::vector<point> &p, std::vector<line> &l,
                      std::unordered_map<int, int> &e) {
  std::map<std::pair<int, int>, int> w;
  for (int i = 0; i < l.size(); i++)
    w[{l[i].a, l[i].b}] = w[{l[i].b, l[i].a}] = i;
  for (int a = 0; a < p.size(); a++)
    for (int b = a + 1; b < p.size(); b++) try_insert_edge(s, p, l, e, w, a, b);
  for (int i = (p.size() > 4 ? 4 : 0); i < p.size(); i++)
    iterate_triangles(i, p, l, e, w,
                      [&](const int a, const int b, const int c, const int i,
                          const int j, const int k) {
                        if (k == -1) return;
                        int &l0 = (l[i].t0 == -1 ? l[i].t0 : l[i].t1);
                        int &l1 = (l[j].t0 == -1 ? l[j].t0 : l[j].t1);
                        int &l2 = (l[k].t0 == -1 ? l[k].t0 : l[k].t1);
                        if (l0 != -1 || l1 != -1 || l2 != -1) return;
                        l0 = l1 = l2 = t.size();
                        t.push_back({a, b, c, o, i, j, k});
                      });
}
static void fill(const std::vector<point> &p, std::vector<line> &l,
                 const std::unordered_map<int, int> &e,
                 std::vector<triangle> &t, const point &q, const int o) {
  std::stack<int> ls, ts;
  int g = -1;
  for (int i = 0; i < l.size(); i++)
    if (l[i].o != -1)
      if (segment_point_intersection({p[l[i].a], p[l[i].b]}, q)) {
        g = l[i].o;
        ls.push(i);
        break;
      }
  if (ls.empty())
    for (int i = 0; i < t.size(); i++)
      if (triangle_point_intersection(p, t[i], q)) {
        g = t[i].o;
        ts.push(i);
        break;
      }
  if (!ls.empty() && l[ls.top()].o == o) return;
  if (!ts.empty() && t[ts.top()].o == o) return;
  while (!ls.empty() || !ts.empty()) {
    while (!ls.empty()) {
      const int i = ls.top();
      ls.pop();
      if (i != -1 && l[i].o == g && l[i].o != o) {
        l[i].o = o;
        ts.push(l[i].t0);
        ts.push(l[i].t1);
        iterate_lines(l[i].a, l, e, [&](const int j) { ls.push(j); });
        iterate_lines(l[i].b, l, e, [&](const int j) { ls.push(j); });
      }
    }
    while (!ts.empty()) {
      const int i = ts.top();
      ts.pop();
      if (i != -1 && t[i].o == g && t[i].o != o) {
        t[i].o = o;
        ls.push(t[i].l0);
        ls.push(t[i].l1);
        ls.push(t[i].l2);
        if (t[i].l0 != -1 && l[t[i].l0].o == -1) {
          ts.push(l[t[i].l0].t0);
          ts.push(l[t[i].l0].t1);
        }
        if (t[i].l1 != -1 && l[t[i].l1].o == -1) {
          ts.push(l[t[i].l1].t0);
          ts.push(l[t[i].l1].t1);
        }
        if (t[i].l2 != -1 && l[t[i].l2].o == -1) {
          ts.push(l[t[i].l2].t0);
          ts.push(l[t[i].l2].t1);
        }
      }
    }
  }
}
static double triangle_area(const std::vector<point> &p, const triangle &t) {
  const long double u = (p[t.a].x - p[t.b].x) * (p[t.c].y - p[t.b].y);
  const long double v = (p[t.c].x - p[t.b].x) * (p[t.a].y - p[t.b].y);
  return 0.5 * std::abs(u - v);
}
int main(int argc, char *argv[]) {
  double w, h;
  int n, m;
  if (scanf("%lf %lf %d", &w, &h, &n) != 3) {
    fprintf(stderr, "fscanf: Header IO error.\n");
    exit(EXIT_FAILURE);
  }
  w *= scale, h *= scale;
  std::map<std::string, int> c;
  std::vector<segment> so(n);
  for (int i = 0; i < n; i++) {
    const int ob = color_index(c, "black");
    double ax, ay, bx, by;
    if (scanf("%lf %lf %lf %lf", &ax, &ay, &bx, &by) != 4) {
      fprintf(stderr, "fscanf: Segment IO error.\n");
      exit(EXIT_FAILURE);
    }
    so[i] = {{ax * scale, ay * scale}, {bx * scale, by * scale}, ob};
  }
  const std::vector<segment> sc = cut_segments(so);
  if (scanf("%d", &m) != 1) {
    fprintf(stderr, "fscanf: Header IO error.\n");
    exit(EXIT_FAILURE);
  }
  std::vector<triangle> t;
  std::vector<point> p;
  std::unordered_map<int, int> e;
  std::vector<line> l;
  p.push_back({0, 0});
  p.push_back({w, 0});
  p.push_back({w, h});
  p.push_back({0, h});
  segments_to_lines(sc, p, l, e);
  tesselate(t, color_index(c, "white"), so, p, l, e);
  for (int i = 0; i < m; i++) {
    double qx, qy;
    char o[101];
    point q;
    if (scanf("%lf %lf %100s", &qx, &qy, o) != 3) {
      fprintf(stderr, "fscanf: Fill IO error.\n");
      exit(EXIT_FAILURE);
    }
    q.x = qx * scale, q.y = qy * scale;
    fill(p, l, e, t, q, color_index(c, o));
  }
  std::map<std::string, double> a;
  for (const line &i : l)
    if (i.o != -1) a[color_name(c, i.o)] += 0.0;
  for (const triangle &i : t) a[color_name(c, i.o)] += triangle_area(p, i);
  for (const std::pair<std::string, double> &i : a)
    printf("%s %.8f\n", i.first.c_str(), i.second / pow(scale, 2));
  return EXIT_SUCCESS;
}