Problem: In the International City of Pipe Construction, it is planned to repair the water pipe at a certain point in the water pipe network. The network consists of water pipe segments, stop valves and source point. A water pipe is represented by a segment on a 2D-plane and intersected pair of water pipe segments are connected at the intersection point. A stop valve, which prevents from water flowing into the repairing point while repairing, is represented by a point on some water pipe segment. In the network, just one source point exists and water is supplied to the network from this point.

Of course, while repairing, we have to stop water supply in some areas, but, in order to reduce the risk of riots, the length of water pipes stopping water supply must be minimized. What you have to do is to write a program to minimize the length of water pipes needed to stop water supply when the coordinates of end points of water pipe segments, stop valves, source point and repairing point are given.



Input

A data set has the following format:

> N M
>  xs1 ys1 xd1 yd1
>  ...
>  xsN ysN xdN ydN
>  xv1 yv1
>  ...
>  xvM yvM
>  xb yb
>  xc yc
>

The first line of the input contains two integers, N (1 ≤ N ≤ 300) and M (0 ≤ M ≤ 1,000) that indicate the number of water pipe segments and stop valves. The following N lines describe the end points of water pipe segments. The i-th line contains four integers, xsi, ysi, xdi and ydi that indicate the pair of coordinates of end points of i-th water pipe segment. The following M lines describe the points of stop valves. The i-th line contains two integers, xvi and yvi that indicate the coordinate of end points of i-th stop valve. The following line contains two integers, xb and yb that indicate the coordinate of the source point. The last line contains two integers, xc and yc that indicate the coordinate of the repairing point.

You may assume that any absolute values of coordinate integers are less than 1,000 (inclusive.) You may also assume each of the stop valves, the source point and the repairing point is always on one of water pipe segments and that that each pair among the stop valves, the source point and the repairing point are different. And, there is not more than one intersection between each pair of water pipe segments. Finally, the water pipe network is connected, that is, all the water pipes are received water supply initially.

Output

Print the minimal length of water pipes needed to stop water supply in a line. The absolute or relative error should be less than or 10-6. When you cannot stop water supply to the repairing point even though you close all stop valves, print "`-1`" in a line.

Examples

Input

1 2
0 0 10 0
1 0
9 0
0 0
5 0


Output

9.0


Input

5 3
0 4 2 4
0 2 2 2
0 0 2 0
0 0 0 4
2 0 2 4
0 2
1 0
2 2
1 4
2 1


Output

3.0


Input

2 1
0 0 0 4
0 2 2 2
1 2
0 1
0 3


Output

-1

Solution (in CPP):

Solution:
// implement 43min
// debug 17min
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <set>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

typedef double Weight;
struct Edge {
  int src;
  int dest;
  Weight weight;
  Edge(int src, int dest, Weight weight) : src(src), dest(dest), weight(weight) {;}
  bool operator<(const Edge &rhs) const {
    if (weight != rhs.weight) { return weight > rhs.weight; }
    if (src != rhs.src) { return src < rhs.src; }
    return dest < rhs.dest;
  }
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef vector<Weight> Array;
typedef vector<Array> Matrix;

void PrintMatrix(const Matrix &matrix) {
  for (int y = 0; y < (int)matrix.size(); y++) {
    for (int x = 0; x < (int)matrix[y].size(); x++) {
      printf("%.2lf ", matrix[y][x]);
    }
    puts("");
  }
}

#include <complex>

typedef complex<double> Point;
typedef vector<Point> Polygon;

static const double INF = 1e+10;

#define CURR(P, i) (P[i])
#define NEXT(P, i) (P[(i + 1) % P.size()])

struct Line : public vector<Point> {
  Line() {;}
  Line(Point a, Point b) { push_back(a); push_back(b); }
};

namespace std {
  bool operator<(const Point &lhs, const Point &rhs) {
    if (fabs(lhs.real() - rhs.real()) < EPS * 10 &&
        fabs(lhs.imag() - rhs.imag()) < EPS * 10) { return false; }
    return lhs.real() == rhs.real() ? lhs.imag() < rhs.imag() : lhs.real() < rhs.real();
  }
}

inline double cross(const Point &a, const Point &b) {
  return imag(conj(a) * b);
}

inline double dot(const Point &a, const Point &b) {
  return real(conj(a) * b);
}

inline int ccw(Point a, Point b, Point c) {
  b -= a;
  c -= a;
  if (cross(b, c) > 0) { return 1; }
  if (cross(b, c) < 0) { return -1; }
  if (dot(b, c) < 0) { return 2; }
  if (norm(b) < norm(c)) { return -2; }
  return 0;
}


bool intersectLL(const Line &l, const Line &m) {
  return abs(cross(l[1] - l[0], m[1] - m[0])) > EPS ||
    abs(cross(l[1] - l[0], m[0] - l[0])) < EPS;
}

bool intersectLS(const Line &l, const Line &s) {
  return cross(l[1] - l[0], s[0] - l[0]) *
    cross(l[1] - l[0], s[1] - l[0]) < EPS;
}

bool intersectLP(const Line &l, const Point &p) {
  return abs(cross(l[1] - p, l[0] - p)) < EPS;
}

bool intersectSS(const Line &s, const Line &t) {
  return ccw(s[0], s[1], t[0]) * ccw(s[0], s[1], t[1]) <= 0 &&
    ccw(t[0], t[1], s[0]) * ccw(t[0], t[1], s[1]) <= 0;
}

bool intersectSP(const Line &s, const Point &p) {
  return abs(s[0] - p) + abs(s[1] - p) - abs(s[1] - s[0]) < EPS;
}

Point crosspointSS(const Line &l, const Line &m) {
  double A = cross(l[1] - l[0], m[1] - m[0]);
  double B = cross(l[1] - l[0], l[1] - m[0]);
  if (abs(A) < EPS && abs(B) < EPS) {
    //assert(false);
    if (intersectSP(l, m[0])) { return m[0]; }
    if (intersectSP(l, m[1])) { return m[1]; }
    if (intersectSP(m, l[0])) { return l[0]; }
    if (intersectSP(m, l[1])) { return l[1]; }
    return m[0];
  }
  if (abs(A) < EPS) { assert(false); }
  return m[0] + B / A * (m[1] - m[0]);
}

double Area(const Polygon &p) {
  double ret = 0;
  for (int i = 0; i < (int)p.size(); i++) {
    ret += cross(CURR(p, i), NEXT(p, i));
  }
  //cout << ret / 2.0 << endl;
  assert(ret > -EPS);
  return ret / 2.0;
}


struct ArrangmentEdge {
  int src;
  int dest;
  Weight weight;
  ArrangmentEdge(int src, int dest, Weight weight) : src(src), dest(dest), weight(weight) {;}
  bool operator<(const ArrangmentEdge &rhs) const {
    return dest < rhs.dest;
  }
};
struct ArrangmentData {
  vector<Point> ps;
  map<Point, int> mapto;
  Graph g;
};
ArrangmentData Arrangment(const vector<Line> &ls, const vector<Point> &ps) {
  // Constraint Check
  {
    // Weight should be double
    Weight w = 0.5;
    assert(w == 0.5);
    // near Point should be used as same point
    Point p1(0, 0);
    Point p2(EPS, EPS);
    assert(!(p1 < p2) && !(p2 < p1));
  }

  int l = ls.size();
  int n = 0;
  ArrangmentData ret;
  // Push Point
  for (int i = 0; i < l; i++) {
    REP(j, 2) {
      if (ret.mapto.count(ls[i][j])) { continue; }
      ret.ps.push_back(ls[i][j]);
      ret.mapto[ls[i][j]] = n++;
    }
  }
  for (int i = 0; i < (int)ps.size(); i++) {
    if (ret.mapto.count(ps[i])) { continue; }
    ret.ps.push_back(ps[i]);
    ret.mapto[ps[i]] = n++;
  }

  // Crosspoint Push
  for (int i = 0; i < l; i++) {
    for (int j = i + 1; j < l; j++) {
      Line s1 = ls[i];
      Line s2 = ls[j];
      if (intersectSS(s1, s2)) {
        Point p = crosspointSS(s1, s2);
        if (ret.mapto.count(p)) { continue; }
        ret.ps.push_back(p);
        ret.mapto[p] = n++;
      }
    }
  }

  // Make Graph
  vector<set<ArrangmentEdge> > tempG(n);
  for (int i = 0; i < l; i++) {
    Line s = ls[i];
    vector<pair<double, int> > onLine;
    for (int j = 0; j < n; j++) {
      if (intersectSP(s, ret.ps[j])) {
        onLine.push_back(make_pair(abs(ret.ps[j] - s[0]), j));
      }
    }
    sort(onLine.begin(), onLine.end());
    for (int j = 0; j < (int)onLine.size() - 1; j++) {
      int from = onLine[j].second;
      int to = onLine[j + 1].second;
      double dist = fabs(onLine[j].first - onLine[j + 1].first);
      tempG[from].insert(ArrangmentEdge(from, to, dist));
      tempG[to].insert(ArrangmentEdge(to, from, dist));
      //cout << from << " " << to << " " << ret.ps[from] << " " << ret.ps[to] << endl;
    }
  }

  // Convert Graph
  ret.g = Graph(n);
  for (int i = 0; i < n; i++) {
    for (set<ArrangmentEdge>::iterator it = tempG[i].begin(); it != tempG[i].end(); it++) {
      ret.g[i].push_back(Edge(it->src, it->dest, it->weight));
    }
  }
  return ret;
}

//============================================================

int n, m;
vector<Line> ls;
vector<Point> stop;
Graph g;
bool isstop[200000];
bool visited[2][200000];

double Bfs(int start, int state) {
  double ret = 0.0;
  queue<int> que;
  que.push(start);
  while (!que.empty()) {
    int from = que.front();
    que.pop();
    if (visited[state][from]) { continue; }
    if (state == 1 && visited[0][from]) { continue; }
    visited[state][from] = true;
    if (state == 0 && isstop[from]) { continue; }
    //cout << start << " " << from << endl;
    FORIT(it, g[from]) {
      int to = it->dest;
      if (visited[state][to]) { continue; }
      //cout << from << " " << to << " " << state << endl;
      ret += it->weight;
      que.push(to);
    }
  }
  return ret;
}


int main() {
  while (scanf("%d %d", &n, &m) > 0) {
    MEMSET(isstop, false);
    MEMSET(visited, false);
    Point start;
    Point end;
    // Init & Input
    ls = vector<Line>(n);
    stop = vector<Point>(m);
    REP(i, n) {
      double x1, y1, x2, y2;
      scanf("%lf %lf %lf %lf", &x1, &y1, &x2, &y2);
      ls[i] = Line(Point(x1, y1), Point(x2, y2));
    }
    REP(i, m) {
      double x, y;
      scanf("%lf %lf", &x, &y);
      stop[i] = Point(x, y);
    }
    {
      double x1, y1, x2, y2;
      scanf("%lf %lf %lf %lf", &x1, &y1, &x2, &y2);
      start = Point(x1, y1);
      end = Point(x2, y2);
    }
    stop.push_back(start);
    stop.push_back(end);
    ArrangmentData data = Arrangment(ls, stop);
    stop.pop_back();
    stop.pop_back();
    g = data.g;
    int s = data.mapto[start];
    int t = data.mapto[end];
    isstop[s] = true;
    FORIT(it, stop) {
      isstop[data.mapto[*it]] = true;
    }
    double ans = 0.0;
    REP(i, g.size()) {
      FORIT(it, g[i]) {
        ans += it->weight / 2.0;
      }
    }
    Bfs(t, 0);
    if (visited[0][s]) {
      puts("-1");
      continue;
    }
    ans -= Bfs(s, 1);
    printf("%.8f\n", ans);
  }
}