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;
class MaxFlow {
 public:
  struct Edge {
    int b, e;
    long double f;
  } E[10100 * 2];
  vector<int> G[2010];
  int Level[2010], Q[2010], PV[2010], source, sink, EC, n;
  long double flow;
  void init(int N, int S, int T) {
    n = N, EC = 0;
    for (int i = 0; i <= n; i++) G[i].clear();
    flow = 0.0;
    source = S, sink = T;
  }
  void Add_Edge(int a, int b, long double f) {
    G[a].push_back(EC);
    G[b].push_back(EC + 1);
    E[EC++] = {a, b, f};
    E[EC++] = {b, a, 0.0};
  }
  bool GetLevel() {
    int i;
    for (i = 1; i <= n; i++) Level[i] = -1;
    int head = 0, tail = 0;
    Q[++tail] = source, Level[source] = 0;
    while (head < tail) {
      int x = Q[++head];
      for (auto &y : G[x]) {
        if (E[y].f > 0 && Level[E[y].e] == -1) {
          Q[++tail] = E[y].e;
          Level[E[y].e] = Level[x] + 1;
        }
      }
    }
    return Level[sink] != -1;
  }
  long double BlockFlow(int a, long double f) {
    if (a == sink) return f;
    long double M = 1e9;
    for (int &i = PV[a]; i >= 0; i--) {
      int x = G[a][i];
      if (E[x].f > 0 && Level[E[x].e] == Level[a] + 1) {
        long double t = BlockFlow(E[x].e, min(f, E[x].f));
        if (t) {
          E[x].f -= t;
          E[x ^ 1].f += t;
          return t;
        }
      }
    }
    return 0.0;
  }
  void Dinic() {
    long double t;
    while (GetLevel()) {
      for (int i = 1; i <= n; i++) PV[i] = G[i].size() - 1;
      while ((t = BlockFlow(source, 1e9)) > 0) flow += t;
    }
  }
} G1;
struct EdEd {
  int b, e, A, B, C, D;
} w[2010];
int n, m;
long double Calc(long double tt) {
  G1.init(n + 2, n + 1, n + 2);
  int i;
  long double sum = 0.0;
  for (i = 0; i < m; i++) {
    long double l = w[i].A * tt + w[i].B, r = w[i].C * tt + w[i].D;
    G1.Add_Edge(w[i].b, w[i].e, r - l);
    G1.Add_Edge(w[i].b, G1.sink, l);
    G1.Add_Edge(G1.source, w[i].e, l);
    sum += l;
  }
  G1.Dinic();
  return sum - G1.flow;
}
long double res;
void Make(long double b, long double e) {
  long double mid;
  for (int i = 0; i < 50; i++) {
    mid = (b + e) * 0.5;
    if (Calc(mid) < 1e-9) {
      long double tp = mid - b;
      res += (tp > 0 ? tp : -tp);
      b = mid;
    } else
      e = mid;
  }
}
int main() {
  int i;
  scanf("%d%d", &n, &m);
  for (i = 0; i < m; i++) {
    scanf("%d%d%d%d%d%d", &w[i].b, &w[i].e, &w[i].A, &w[i].B, &w[i].C, &w[i].D);
  }
  long double be = 0.0, ed = 1.0, m1, m2;
  for (int tt = 0; tt < 50; tt++) {
    m1 = (be * 2 + ed) / 3;
    m2 = (be + ed * 2) / 3;
    long double t1 = Calc(m1);
    long double t2 = Calc(m2);
    if (t1 < 1e-9 && t2 < 1e-9) {
      Make((m1 + m2) * 0.5, 0);
      Make((m1 + m2) * 0.5, 1);
      break;
    }
    if (t1 < t2)
      ed = m2;
    else
      be = m1;
  }
  printf("%.10Lf\n", res);
}