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>
inline int pidorand() { return ((rand() & 32767) << 15) | (rand() & 32767); }
using namespace std;
inline int nxt() {
  int x;
  scanf("%d", &x);
  return x;
}
struct Edge {
  int from, to;
  long long cap, flow;
};
const int INF = (int)2e9;
struct Dinic {
  int n;
  int s, t;
  vector<Edge> edges;
  vector<vector<int>> g;
  Dinic(int n, int s, int t) : n(n), s(s), t(t) { g.resize(n); }
  void add_edge(int from, int to, long long cap) {
    Edge e = {from, to, cap, 0};
    g[from].push_back(edges.size());
    edges.push_back(e);
    e = {to, from, 0, 0};
    g[to].push_back(edges.size());
    edges.push_back(e);
  }
  vector<int> d;
  bool bfs(int s, int t) {
    d.assign(n, INF);
    d[s] = 0;
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
      int v = q.front();
      q.pop();
      for (auto id : g[v]) {
        auto e = edges[id];
        if (e.cap > e.flow && d[e.to] == INF) {
          d[e.to] = d[v] + 1;
          q.push(e.to);
        }
      }
    }
    return d[t] != INF;
  }
  vector<int> pointer;
  long long dfs(int v, int t, long long flow_add) {
    if (!flow_add) {
      return 0;
    }
    if (v == t) {
      return flow_add;
    }
    for (int& i = pointer[v]; i < (int)g[v].size(); ++i) {
      int id = g[v][i];
      int to = edges[id].to;
      if (d[to] != d[v] + 1) {
        continue;
      }
      long long pushed =
          dfs(to, t, min(flow_add, edges[id].cap - edges[id].flow));
      if (pushed) {
        edges[id].flow += pushed;
        edges[id ^ 1].flow -= pushed;
        return pushed;
      }
    }
    return 0;
  }
  long long get_flow() {
    long long flow = 0;
    while (bfs(s, t)) {
      pointer.assign(n, 0);
      while (long long pushed = dfs(s, t, INF)) {
        flow += pushed;
      }
    }
    return flow;
  }
};
using Network = Dinic;
int main() {
  int n = nxt();
  int m = nxt();
  vector<array<int, 6>> ed(m);
  for (int i = 0; i < m; ++i) {
    for (int j = 0; j < 6; ++j) {
      ed[i][j] = nxt();
    }
  }
  const long long many = 10000000;
  auto get = [&](long long t) {
    Network net(n + 2, 0, n + 1);
    for (auto e : ed) {
      net.add_edge(0, e[1], e[2] * t + e[3] * many);
      net.add_edge(e[0], n + 1, e[2] * t + e[3] * many);
      net.add_edge(e[0], e[1],
                   e[4] * t + e[5] * many - (e[2] * t + e[3] * many));
    }
    long long res = net.get_flow();
    for (auto e : ed) {
      res -= e[2] * t + e[3] * many;
    }
    return res;
  };
  int l = 0, r = many;
  while (r > l + 2) {
    int m1 = (2 * l + r) / 3;
    int m2 = (l + 2 * r) / 3;
    if (get(m1) > get(m2)) {
      r = m2;
    } else {
      l = m1;
    }
  }
  int mid = l;
  for (int i = l + 1; i <= r; ++i) {
    if (get(i) > get(mid)) {
      mid = i;
    }
  }
  if (get(mid) < 0) {
    puts("0");
    return 0;
  }
  l = mid, r = many + 1;
  while (r > l + 1) {
    int m = (l + r) / 2;
    if (get(m) == 0) {
      l = m;
    } else {
      r = m;
    }
  }
  int ans = l;
  l = -1, r = mid;
  while (r > l + 1) {
    int m = (l + r) / 2;
    if (get(m) == 0) {
      r = m;
    } else {
      l = m;
    }
  }
  ans -= r;
  cout << setprecision(10) << fixed;
  cout << 1.0 * ans / many << "\n";
  return 0;
}