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>
#pragma GCC optimize "-O3"
using namespace std;
const double eps = 1e-11;
template <typename T>
struct Dinic {
  const T INF = 1e9;
  const int INF1 = 1e9;
  struct edge {
    int a, b;
    T f, c;
  };
  int s, t;
  vector<edge> ed;
  int n;
  vector<vector<int> > eds;
  vector<T> dd;
  vector<int> pp;
  vector<int> inCut;
  Dinic(int N, int S, int TT) {
    n = N, s = S, t = TT;
    eds.clear();
    dd.clear();
    pp.clear();
    ed.clear();
    eds.resize(n);
    dd.resize(n);
    pp.resize(n);
    inCut.clear();
  }
  void add_edge(int a, int b, T c) {
    edge x;
    x.a = a;
    x.b = b;
    x.f = 0;
    x.c = c;
    eds[a].push_back(ed.size());
    eds[b].push_back(ed.size() + 1);
    ed.push_back(x);
    x.c = 0;
    swap(x.a, x.b);
    ed.push_back(x);
  }
  T dfs(int v, T fl) {
    if (v == t) return fl;
    if (dd[v] == dd[t]) return 0;
    T sum = 0;
    for (; pp[v] < (int)eds[v].size(); ++pp[v]) {
      int e = eds[v][pp[v]];
      int u = ed[e].b;
      T fr = ed[e].c - ed[e].f;
      if (fr <= eps || dd[u] != dd[v] + 1 || pp[u] == (int)eds[u].size())
        continue;
      fr = dfs(u, min(fl, fr));
      ed[e].f += fr;
      ed[e ^ 1].f -= fr;
      sum += fr;
      fl -= fr;
      if (fl <= eps) break;
    }
    return sum;
  }
  T flow() {
    T sum = 0;
    T lst = 0;
    do {
      lst = 0;
      fill(dd.begin(), dd.end(), INF1);
      dd[s] = 0;
      queue<int> qu;
      qu.push(s);
      while (!qu.empty()) {
        int x = qu.front();
        qu.pop();
        for (int i = 0; i < (int)eds[x].size(); ++i) {
          if (ed[eds[x][i]].f < ed[eds[x][i]].c) {
            int u = ed[eds[x][i]].b;
            if (dd[u] > dd[x] + 1) dd[u] = dd[x] + 1, qu.push(u);
          }
        }
      }
      if (dd[t] == INF) break;
      fill(pp.begin(), pp.end(), 0);
      lst = dfs(s, INF);
      sum += lst;
    } while (lst > 0);
    return sum;
  }
  void dfs1(int s) {
    pp[s] = 1;
    for (int e : eds[s]) {
      if (abs(ed[e].c - ed[e].f) > eps && !pp[ed[e].b]) dfs1(ed[e].b);
    }
  }
  void markCut() {
    inCut.resize(ed.size());
    fill(pp.begin(), pp.end(), 0);
    dfs1(s);
    for (int i = 0; i < ed.size(); ++i)
      if (pp[ed[i].a] && !pp[ed[i].b])
        inCut[i] = 1;
      else
        inCut[i] = 0;
  }
};
int n, m;
vector<tuple<int, int, long long, long long> > edd;
vector<tuple<int, int, long long, long long, long long, long long> > edd2;
pair<long long, long long> ad[1200];
const int IT = 50;
int main() {
  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cout.setf(ios::fixed), cout.precision(20);
  cin >> n >> m;
  for (int i = 0; i < m; ++i) {
    int u, v;
    long long a, b, c, d;
    cin >> u >> v >> a >> b >> c >> d;
    --u, --v;
    edd.push_back(make_tuple(u, v, c - a, d - b));
    edd2.push_back(make_tuple(u, v, a, b, c, d));
    ad[u].first -= a;
    ad[u].second -= b;
    ad[v].first += a;
    ad[v].second += b;
  }
  double lb = 0;
  double rb = 1;
  double ans = -1;
  for (int it = 0; it < IT; ++it) {
    double mid = (lb + rb) / 2;
    Dinic<double> din(n + 2, n, n + 1);
    for (auto x : edd) {
      int u, v;
      long long a, b;
      tie(u, v, a, b) = x;
      din.add_edge(u, v, a * mid + b);
    }
    double go = 0;
    for (int i = 0; i < n; ++i) {
      double x = ad[i].first * mid + ad[i].second;
      if (x > 0) {
        din.add_edge(n, i, x);
        go += x;
      } else if (x < 0) {
        din.add_edge(i, n + 1, -x);
      }
    }
    double xx = din.flow();
    if (abs(xx - go) <= eps) {
      ans = mid;
      break;
    }
    din.markCut();
    pair<double, double> cur = make_pair(0, 0);
    for (auto x : edd2) {
      int u, v;
      long long a, b, c, d;
      tie(u, v, a, b, c, d) = x;
      if (din.pp[u] && !din.pp[v]) {
        cur.first += c;
        cur.second += d;
      } else if (din.pp[v] && !din.pp[u]) {
        cur.first -= a;
        cur.second -= b;
      }
    }
    if (cur.first == 0) break;
    if (cur.first > 0)
      lb = mid;
    else
      rb = mid;
  }
  if (ans < -0.5) {
    cout << 0 << "\n";
    return 0;
  }
  lb = 0;
  rb = ans;
  for (int it = 0; it < IT; ++it) {
    double mid = (lb + rb) / 2;
    Dinic<double> din(n + 2, n, n + 1);
    for (auto x : edd) {
      int u, v;
      long long a, b;
      tie(u, v, a, b) = x;
      din.add_edge(u, v, a * mid + b);
    }
    double go = 0;
    for (int i = 0; i < n; ++i) {
      double x = ad[i].first * mid + ad[i].second;
      if (x > 0) {
        din.add_edge(n, i, x);
        go += x;
      } else if (x < 0) {
        din.add_edge(i, n + 1, -x);
      }
    }
    double xx = din.flow();
    if (abs(xx - go) <= eps)
      rb = mid;
    else
      lb = mid;
  }
  double l = (lb + rb) / 2;
  lb = ans;
  rb = 1;
  for (int it = 0; it < IT; ++it) {
    double mid = (lb + rb) / 2;
    Dinic<double> din(n + 2, n, n + 1);
    for (auto x : edd) {
      int u, v;
      long long a, b;
      tie(u, v, a, b) = x;
      din.add_edge(u, v, a * mid + b);
    }
    double go = 0;
    for (int i = 0; i < n; ++i) {
      double x = ad[i].first * mid + ad[i].second;
      if (x > 0) {
        din.add_edge(n, i, x);
        go += x;
      } else if (x < 0) {
        din.add_edge(i, n + 1, -x);
      }
    }
    double xx = din.flow();
    if (abs(xx - go) <= eps)
      lb = mid;
    else
      rb = mid;
  }
  double r = (lb + rb) / 2;
  cout << r - l << "\n";
  return 0;
}