Problem: Vova has recently learned what a circulaton in a graph is. Recall the definition: let G = (V, E) be a directed graph. A circulation f is such a collection of non-negative real numbers f_e (e ∈ E), that for each vertex v ∈ V the following conservation condition holds:

$$$∑_{e ∈ \delta^{-}(v)} f_e = ∑_{e ∈ \delta^{+}(v)} f_e$$$

where \delta^{+}(v) is the set of edges that end in the vertex v, and \delta^{-}(v) is the set of edges that start in the vertex v. In other words, for each vertex the total incoming flow should be equal to the total outcoming flow.

Let a lr-circulation be such a circulation f that for each edge the condition l_e ≤ f_e ≤ r_e holds, where l_e and r_e for each edge e ∈ E are two non-negative real numbers denoting the lower and upper bounds on the value of the circulation on this edge e.

Vova can't stop thinking about applications of a new topic. Right now he thinks about the following natural question: let the graph be fixed, and each value l_e and r_e be a linear function of a real variable t:

$$$l_e(t) = a_e t + b_e r_e(t) = c_e t + d_e$$$

Note that t is the same for all edges.

Let t be chosen at random from uniform distribution on a segment [0, 1]. What is the probability of existence of lr-circulation in the graph?

Input

The first line contains two integers n, m (1 ≤ n ≤ 1000, 1 ≤ m ≤ 2000).

Each of the next m lines describes edges of the graph in the format u_e, v_e, a_e, b_e, c_e, d_e (1 ≤ u_e, v_e ≤ n, -10^4 ≤ a_e, c_e ≤ 10^4, 0 ≤ b_e, d_e ≤ 10^4), where u_e and v_e are the startpoint and the endpoint of the edge e, and the remaining 4 integers describe the linear functions for the upper and lower bound of circulation.

It is guaranteed that for any t ∈ [0, 1] and for any edge e ∈ E the following condition holds 0 ≤ l_e(t) ≤ r_e(t) ≤ 10^4.

Output

Print a single real integer — the probability of existence of lr-circulation in the graph, given that t is chosen uniformly at random from the segment [0, 1]. Your answer is considered correct if its absolute difference from jury's answer is not greater than 10^{-6}.

Example

Input

3 3
1 2 0 3 -4 7
2 3 -2 5 1 6
3 1 0 4 0 4


Output

0.25

Note

In the first example the conservation condition allows only circulations with equal values f_e for all three edges. The value of circulation on the last edge should be 4 whatever t is chosen, so the probability is

$$$P(4 ∈ [3, -4t + 7]~~\&~~4 ∈ [-2t + 5, t + 6]) = 0.25$$$

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
const int MAXM = 3005;
const double inf = 1e8;
const double eps = 1e-8;
template <typename T>
inline void read(T &AKNOI) {
  T x = 0, flag = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') flag = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  AKNOI = flag * x;
}
int n, m, U[MAXM], V[MAXM], A[MAXM], B[MAXM], C[MAXM], D[MAXM];
struct Edge {
  int v, nxt;
  double w;
} e[MAXM << 1];
int first[MAXN], used[MAXN], eCnt;
inline void AddEdge(int u, int v, double w) {
  e[++eCnt].v = v;
  e[eCnt].w = w;
  e[eCnt].nxt = first[u];
  first[u] = eCnt;
}
inline void Add(int u, int v, double w) {
  AddEdge(u, v, w);
  AddEdge(v, u, 0);
}
double in[MAXN];
int S, T, level[MAXN], q[MAXN], head, tail;
bool BFS() {
  for (int i = 1; i <= T; ++i) {
    level[i] = -1;
    used[i] = first[i];
  }
  level[S] = 0;
  q[head = tail = 1] = S;
  while (head <= tail) {
    int u = q[head++];
    if (u == T) return 1;
    for (int i = first[u]; i; i = e[i].nxt) {
      int v = e[i].v;
      if (e[i].w > eps && level[v] == -1) {
        level[v] = level[u] + 1;
        q[++tail] = v;
      }
    }
  }
  return 0;
}
double DFS(int u, double flow) {
  if (u == T) return flow;
  double ret = 0;
  for (int i = used[u]; i; i = e[i].nxt, used[u] = i) {
    int v = e[i].v;
    if (e[i].w > eps && level[v] == level[u] + 1) {
      double tmp = DFS(v, min(flow, e[i].w));
      e[i].w -= tmp;
      e[i ^ 1].w += tmp;
      flow -= tmp;
      ret += tmp;
      if (flow < eps) break;
    }
  }
  return ret;
}
double Check(double mid) {
  eCnt = 1;
  for (int i = 1; i <= T; ++i) {
    in[i] = first[i] = 0;
  }
  for (int i = 1; i <= m; ++i) {
    double l = mid * A[i] + B[i];
    double r = mid * C[i] + D[i];
    Add(U[i], V[i], r - l);
    in[V[i]] += l;
    in[U[i]] -= l;
  }
  double ret = 0;
  for (int i = 1; i <= n; ++i) {
    if (in[i] > eps) {
      ret += in[i];
      Add(S, i, in[i]);
    } else if (in[i] < -eps) {
      Add(i, T, -in[i]);
    }
  }
  while (BFS()) {
    ret -= DFS(S, inf);
  }
  return ret;
}
void init() {
  read(n);
  read(m);
  for (int i = 1; i <= m; ++i) {
    read(U[i]);
    read(V[i]);
    read(A[i]);
    read(B[i]);
    read(C[i]);
    read(D[i]);
  }
  S = n + 1, T = S + 1;
}
void solve() {
  double L = 0, R = 1, ok = -1;
  while (R - L > eps) {
    double M1 = L + (R - L) / 3, M2 = R - (R - L) / 3;
    double D1 = Check(M1), D2 = Check(M2);
    if (D1 < eps) {
      ok = M1;
      break;
    }
    if (D2 < eps) {
      ok = M2;
      break;
    }
    (D1 > D2) ? L = M1 : R = M2;
  }
  if (ok < 0) {
    printf("0\n");
    return;
  }
  double L1 = 0, R1 = ok;
  while (R1 - L1 > eps) {
    double M = (L1 + R1) / 2;
    (Check(M) > eps) ? L1 = M : R1 = M;
  }
  double L2 = ok, R2 = 1;
  while (R2 - L2 > eps) {
    double M = (L2 + R2) / 2;
    (Check(M) > eps) ? R2 = M : L2 = M;
  }
  printf("%.8lf\n", L2 - L1);
}
int main() {
  init();
  solve();
  return 0;
}