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>
using namespace std;
#pragma comment(linker, "/STACK:36777216")
#pragma GCC optimize("O2")
template <class T>
inline void RD(T &);
template <class T>
inline void OT(const T &);
template <class T>
inline T &_RD(T &x) {
  RD(x);
  return x;
}
inline int RD() {
  int x;
  RD(x);
  return x;
}
inline long long RD_LL() {
  long long x;
  RD(x);
  return x;
}
inline double RD_DB() {
  double x;
  RD(x);
  return x;
}
template <class T0, class T1>
inline void RD(T0 &x0, T1 &x1) {
  RD(x0), RD(x1);
}
template <class T0, class T1, class T2>
inline void RD(T0 &x0, T1 &x1, T2 &x2) {
  RD(x0), RD(x1), RD(x2);
}
template <class T0, class T1, class T2, class T3>
inline void RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3) {
  RD(x0), RD(x1), RD(x2), RD(x3);
}
template <class T0, class T1, class T2, class T3, class T4>
inline void RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4) {
  RD(x0), RD(x1), RD(x2), RD(x3), RD(x4);
}
template <class T0, class T1, class T2, class T3, class T4, class T5>
inline void RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5) {
  RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5);
}
template <class T0, class T1, class T2, class T3, class T4, class T5, class T6>
inline void RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5, T6 &x6) {
  RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5), RD(x6);
}
template <class T0, class T1>
inline void OT(T0 &x0, T1 &x1) {
  OT(x0), OT(x1);
}
template <class T0, class T1, class T2>
inline void OT(T0 &x0, T1 &x1, T2 &x2) {
  OT(x0), OT(x1), OT(x2);
}
template <class T0, class T1, class T2, class T3>
inline void OT(T0 &x0, T1 &x1, T2 &x2, T3 &x3) {
  OT(x0), OT(x1), OT(x2), OT(x3);
}
template <class T0, class T1, class T2, class T3, class T4>
inline void OT(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4) {
  OT(x0), OT(x1), OT(x2), OT(x3), OT(x4);
}
template <class T0, class T1, class T2, class T3, class T4, class T5>
inline void OT(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5) {
  OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5);
}
template <class T0, class T1, class T2, class T3, class T4, class T5, class T6>
inline void OT(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5, T6 &x6) {
  OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5), OT(x6);
}
template <class T>
inline void RST(T &A) {
  memset(A, 0, sizeof(A));
}
template <class T0, class T1>
inline void RST(T0 &A0, T1 &A1) {
  RST(A0), RST(A1);
}
template <class T0, class T1, class T2>
inline void RST(T0 &A0, T1 &A1, T2 &A2) {
  RST(A0), RST(A1), RST(A2);
}
template <class T0, class T1, class T2, class T3>
inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3) {
  RST(A0), RST(A1), RST(A2), RST(A3);
}
template <class T0, class T1, class T2, class T3, class T4>
inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4) {
  RST(A0), RST(A1), RST(A2), RST(A3), RST(A4);
}
template <class T0, class T1, class T2, class T3, class T4, class T5>
inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5) {
  RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5);
}
template <class T0, class T1, class T2, class T3, class T4, class T5, class T6>
inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6) {
  RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5), RST(A6);
}
template <class T>
inline void CLR(T &A) {
  A.clear();
}
template <class T0, class T1>
inline void CLR(T0 &A0, T1 &A1) {
  CLR(A0), CLR(A1);
}
template <class T0, class T1, class T2>
inline void CLR(T0 &A0, T1 &A1, T2 &A2) {
  CLR(A0), CLR(A1), CLR(A2);
}
template <class T0, class T1, class T2, class T3>
inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3) {
  CLR(A0), CLR(A1), CLR(A2), CLR(A3);
}
template <class T0, class T1, class T2, class T3, class T4>
inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4) {
  CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4);
}
template <class T0, class T1, class T2, class T3, class T4, class T5>
inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5) {
  CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4), CLR(A5);
}
template <class T0, class T1, class T2, class T3, class T4, class T5, class T6>
inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6) {
  CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4), CLR(A5), CLR(A6);
}
template <class T>
inline void CLR(T &A, int n) {
  for (int i = 0; i < int(n); ++i) CLR(A[i]);
}
template <class T>
inline void FLC(T &A, int x) {
  memset(A, x, sizeof(A));
}
template <class T0, class T1>
inline void FLC(T0 &A0, T1 &A1, int x) {
  FLC(A0, x), FLC(A1, x);
}
template <class T0, class T1, class T2>
inline void FLC(T0 &A0, T1 &A1, T2 &A2) {
  FLC(A0), FLC(A1), FLC(A2);
}
template <class T0, class T1, class T2, class T3>
inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3) {
  FLC(A0), FLC(A1), FLC(A2), FLC(A3);
}
template <class T0, class T1, class T2, class T3, class T4>
inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4) {
  FLC(A0), FLC(A1), FLC(A2), FLC(A3), FLC(A4);
}
template <class T0, class T1, class T2, class T3, class T4, class T5>
inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5) {
  FLC(A0), FLC(A1), FLC(A2), FLC(A3), FLC(A4), FLC(A5);
}
template <class T0, class T1, class T2, class T3, class T4, class T5, class T6>
inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6) {
  FLC(A0), FLC(A1), FLC(A2), FLC(A3), FLC(A4), FLC(A5), FLC(A6);
}
template <class T>
inline void SRT(T &A) {
  sort(A.begin(), A.end());
}
template <class T, class C>
inline void SRT(T &A, C B) {
  sort(A.begin(), A.end(), B);
}
const int MOD = 1000000007;
const int INF = 0x7fffffff;
const double PI = acos(-1.0);
const double EPS = 1e-6;
const double OO = 1e15;
template <class T>
inline void checkMin(T &a, const T b) {
  if (b < a) a = b;
}
template <class T>
inline void checkMax(T &a, const T b) {
  if (b > a) a = b;
}
template <class T, class C>
inline void checkMin(T &a, const T b, C c) {
  if (c(b, a)) a = b;
}
template <class T, class C>
inline void checkMax(T &a, const T b, C c) {
  if (c(a, b)) a = b;
}
template <class T>
inline T min(T a, T b, T c) {
  return min(min(a, b), c);
}
template <class T>
inline T max(T a, T b, T c) {
  return max(max(a, b), c);
}
template <class T>
inline T sqr(T a) {
  return a * a;
}
template <class T>
inline T cub(T a) {
  return a * a * a;
}
int Ceil(int x, int y) { return (x - 1) / y + 1; }
inline bool _1(int x, int i) { return x & 1 << i; }
inline int _1(int i) { return 1 << i; }
inline int _U(int i) { return _1(i) - 1; };
inline int count_bits(int x) {
  x = (x & 0x55555555) + ((x & 0xaaaaaaaa) >> 1);
  x = (x & 0x33333333) + ((x & 0xcccccccc) >> 2);
  x = (x & 0x0f0f0f0f) + ((x & 0xf0f0f0f0) >> 4);
  x = (x & 0x00ff00ff) + ((x & 0xff00ff00) >> 8);
  x = (x & 0x0000ffff) + ((x & 0xffff0000) >> 16);
  return x;
}
template <class T>
inline T low_bit(T x) {
  return x & -x;
}
template <class T>
inline T high_bit(T x) {
  T p = low_bit(x);
  while (p != x) x -= p, p = low_bit(x);
  return p;
}
inline void INC(int &a, int b) {
  a += b;
  if (a >= MOD) a -= MOD;
}
inline int sum(int a, int b) {
  a += b;
  if (a >= MOD) a -= MOD;
  return a;
}
inline void DEC(int &a, int b) {
  a -= b;
  if (a < 0) a += MOD;
}
inline int dff(int a, int b) {
  a -= b;
  if (a < 0) a += MOD;
  return a;
}
inline void MUL(int &a, int b) { a = (long long)a * b % MOD; }
inline int pdt(int a, int b) { return (long long)a * b % MOD; }
template <class T>
inline void RD(T &x) {
  cin >> x;
}
int ____Case;
template <class T>
inline void OT(const T &x) {
  cout << x << endl;
}
int sgn(double x) { return x < -EPS ? -1 : x > EPS; }
struct Po {
  double x, y;
  Po() {}
  Po(double _x, double _y) : x(_x), y(_y) {}
  bool operator<(const Po &rhs) const {
    return sgn(x - rhs.x) < 0 || !sgn(x - rhs.x) && sgn(y - rhs.y) < 0;
  }
  bool operator==(const Po &rhs) const {
    return !sgn(x - rhs.x) && !sgn(y - rhs.y);
  }
  bool operator!=(const Po &rhs) const { return !(*this == rhs); }
  void input() { scanf("%lf%lf", &x, &y); }
};
struct line {
  Po x, y;
  line() {}
  line(Po _x, Po _y) : x(_x), y(_y) {}
  void input() { x.input(), y.input(); }
};
struct node {
  string c;
  vector<int> a;
  double sz;
  node(string _c, double _sz = 0) : c(_c), sz(_sz) {}
  void add(int x) { a.push_back(x); }
};
Po med(Po a, Po b, Po c) {
  if (a < b)
    if (b < c)
      return b;
    else if (a < c)
      return c;
    else
      return a;
  else if (a < c)
    return a;
  else if (b < c)
    return c;
  else
    return b;
}
int getcrs(line a, line b, Po &c) {
  double A = a.y.y - a.x.y, B = a.x.x - a.y.x, C = a.x.x * A + a.x.y * B;
  double D = b.y.y - b.x.y, E = b.x.x - b.y.x, F = b.x.x * D + b.x.y * E;
  if (fabs(A * E - B * D) < EPS) return -1;
  c = Po((C * E - F * B) / (A * E - D * B), (C * D - F * A) / (B * D - E * A));
  if (med(a.x, a.y, c) != c || med(b.x, b.y, c) != c) return -1;
  return 0;
}
bool online(Po p, line a) {
  if (med(a.x, a.y, p) != p) return 0;
  double A = a.y.y - a.x.y, B = a.x.x - a.y.x, C = a.x.x * A + a.x.y * B;
  return abs(A * p.x + B * p.y - C) < EPS;
}
double ang(Po a, Po b) {
  double S = atan2(b.y - a.y, b.x - a.x) * 180 / M_PI;
  if (S < EPS) S += 360;
  return S;
}
bool cmpid(const pair<int, double> &a, const pair<int, double> &b) {
  return a.first < b.first;
}
bool equid(const pair<int, double> &a, const pair<int, double> &b) {
  return a.first == b.first;
}
bool cmpang(const pair<int, double> &a, const pair<int, double> &b) {
  return a.second < b.second;
}
double getsz(vector<Po> p) {
  double S = 0;
  for (int i = 0; i < (int)p.size(); i++) {
    int j = (i + 1) % (int)p.size();
    S += p[i].x * p[j].y - p[j].x * p[i].y;
  }
  return -S / 2;
}
double crs(Po a, Po b, Po c) {
  return (b.y - a.y) * (c.x - a.x) - (b.x - a.x) * (c.y - a.y);
}
int inpoly(Po p, vector<Po> a) {
  int n = (int)a.size();
  a.push_back(a[0]);
  for (int i = 0; i < n; i++)
    if (online(p, line(a[i], a[i + 1]))) return 0;
  int w = 0;
  for (int i = 0; i < n; i++)
    if (a[i].y <= p.y && a[i + 1].y > p.y && crs(a[i], a[i + 1], p) < 0)
      ++w;
    else if (a[i].y > p.y && a[i + 1].y <= p.y && crs(a[i], a[i + 1], p) > 0)
      --w;
  return w;
}
int w, h, n, m, p;
vector<Po> po;
vector<vector<pair<int, double> > > pa;
vector<node> gr;
vector<int> bl;
vector<Po> fl;
vector<vector<Po> > pl;
void bfs(int x, string c) {
  string d = gr[x].c;
  queue<int> q;
  vector<bool> v((int)gr.size(), 0);
  v[x] = 1, q.push(x);
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    gr[x].c = c;
    for (int i = 0; i < (int)gr[x].a.size(); i++)
      if (!v[gr[x].a[i]] && gr[gr[x].a[i]].c == d)
        q.push(gr[x].a[i]), v[gr[x].a[i]] = 1;
  }
}
int main() {
  RD(w, h, n);
  vector<line> l0(n);
  for (int i = 0; i < int(n); ++i) l0[i].input();
  for (int i = 0; i < n; i++) po.push_back(l0[i].x), po.push_back(l0[i].y);
  for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++) {
      Po p;
      if (getcrs(l0[i], l0[j], p) != -1) po.push_back(p);
    }
  sort(po.begin(), po.end()), po.erase(unique(po.begin(), po.end()), po.end());
  m = (int)po.size();
  pa.resize(m);
  for (int i = 0; i < n; i++) {
    vector<int> vp;
    for (int j = 0; j < m; j++)
      if (online(po[j], l0[i])) vp.push_back(j);
    for (int j = 1; j < (int)vp.size(); j++)
      pa[vp[j - 1]].push_back(make_pair(vp[j], ang(po[vp[j - 1]], po[vp[j]]))),
          pa[vp[j]].push_back(
              make_pair(vp[j - 1], ang(po[vp[j]], po[vp[j - 1]])));
  }
  for (int i = 0; i < m; i++)
    sort(pa[i].begin(), pa[i].end(), cmpid),
        pa[i].erase(unique(pa[i].begin(), pa[i].end(), equid), pa[i].end()),
        sort(pa[i].begin(), pa[i].end(), cmpang);
  gr.push_back(node("white", w * h));
  fl.push_back(Po(0.0, 0.0));
  bl.resize(m, -1);
  for (int i = 0; i < m; i++)
    if (bl[i] == -1) {
      queue<int> q;
      q.push(i);
      gr.push_back(node("black", 0.0));
      bl[i] = ++p, fl.push_back(po[i]);
      while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int j = 0; j < (int)pa[x].size(); j++)
          if (bl[pa[x][j].first] == -1)
            q.push(pa[x][j].first), bl[pa[x][j].first] = p;
      }
    }
  pl.resize(p + 1);
  vector<vector<bool> > chk(m);
  for (int i = 0; i < m; i++) chk[i].resize((int)pa[i].size(), 0);
  for (int i = 0; i < m; i++)
    for (int j = 0; j < (int)pa[i].size(); j++) {
      if (chk[i][j]) continue;
      vector<Po> vp;
      int i0 = i, j0 = j;
      while (!chk[i0][j0]) {
        vp.push_back(po[i0]);
        chk[i0][j0] = 1;
        int i1 = pa[i0][j0].first, j1 = -1;
        for (int j = 0; j < (int)pa[i1].size(); j++)
          if (pa[i1][j].first == i0) {
            j1 = (j + 1) % (int)pa[i1].size();
            break;
          }
        i0 = i1, j0 = j1;
      }
      double sz = getsz(vp);
      if (sz > 0) {
        pl.push_back(vp);
        gr.push_back(node("white", sz));
        int r = bl[i];
        gr[r].add((int)gr.size() - 1), gr[(int)gr.size() - 1].add(r);
        gr[r].sz -= sz;
      }
    }
  for (int i = 1; i <= p; i++) {
    int fa = 0;
    for (int j = (int)pl.size() - 1; j > p; j--)
      if (inpoly(fl[i], pl[j])) {
        fa = j;
        break;
      }
    gr[fa].add(i), gr[i].add(fa), gr[fa].sz += gr[i].sz, gr[i].sz = 0;
  }
  int _;
  scanf("%d", &_);
  while (_--) {
    Po x;
    x.input();
    string c;
    char s[100];
    scanf("%s", s), c = s;
    for (int i = 0; i < m; i++)
      for (int j = 0; j < (int)pa[i].size(); j++)
        if (online(x, line(po[i], po[pa[i][j].first]))) {
          bfs(bl[i], c);
          goto end;
        }
    for (int i = (int)pl.size() - 1; i > p; i--)
      if (inpoly(x, pl[i])) {
        bfs(i, c);
        goto end;
      }
    bfs(0, c);
  end:;
  }
  map<string, double> S;
  for (int i = 0; i < (int)gr.size(); i++) S[gr[i].c] += gr[i].sz;
  for (__typeof(S.begin()) it = S.begin(); it != S.end(); ++it) {
    printf("%s %.9lf\n", it->first.c_str(), it->second);
  }
  return 0;
}