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 NMAX = 1005;
const int MMAX = 2005;
const double EPS = 1e-7;
template <class CapacityType>
class MaxFlow {
 private:
  static constexpr int NIL = -1;
  static constexpr double EPS = 1e-7;
  static constexpr int INF = std::numeric_limits<int>::max() / 2;
  template <class type>
  int cmp(type x) {
    if (-EPS < x and x < EPS) return 0;
    return x < 0 ? -1 : 1;
  }
  struct Edge {
    int nod, nxt;
    CapacityType cap;
    Edge() : nod(0), nxt(0), cap(0){};
    Edge(int _nod, int _nxt, CapacityType _cap)
        : nod(_nod), nxt(_nxt), cap(_cap){};
  };
  std::vector<Edge> lst;
  std::vector<bool> oki;
  int ptr = 0;
  std::vector<int> beg, que, adj, dis;
  bool bfs(const int src, const int dst) {
    std::fill(dis.begin(), dis.end(), (CapacityType)INF);
    dis[src] = 0;
    que[0] = src;
    for (int qbg = 0, qen = 0; qbg <= qen; ++qbg) {
      const int x = que[qbg];
      for (int it = beg[x]; it != NIL; it = lst[it].nxt) {
        const int y = lst[it].nod;
        if (cmp(lst[it].cap) > 0 and dis[y] == INF)
          dis[y] = dis[x] + 1, que[++qen] = y;
      }
    }
    return dis[dst] != INF;
  }
  CapacityType dfs(const int x, const int dst, const CapacityType cap) {
    if (!cmp(cap) or x == dst) return cap;
    for (; adj[x] != NIL; adj[x] = lst[adj[x]].nxt) {
      const int y = lst[adj[x]].nod;
      if (cmp(lst[adj[x]].cap) > 0 and dis[y] == dis[x] + 1) {
        const CapacityType aux = dfs(y, dst, std::min(cap, lst[adj[x]].cap));
        if (cmp(aux)) {
          lst[adj[x]].cap -= aux;
          lst[adj[x] ^ 1].cap += aux;
          return aux;
        }
      }
    }
    return 0;
  }
  void fill(const int x) {
    oki[x] = true;
    for (int it = beg[x]; it != NIL; it = lst[it].nxt) {
      const int y = lst[it].nod;
      if (cmp(lst[it].cap) > 0 and !oki[y]) fill(y);
    }
  }

 public:
  MaxFlow(int szn, int szm) {
    dis.resize(szn);
    beg.resize(szn);
    que.resize(szn);
    adj.resize(szn);
    oki.resize(szn);
    lst.resize(szm);
    std::fill(beg.begin(), beg.end(), (int)NIL);
  }
  inline void addDirectedEdge(const int x, const int y,
                              const CapacityType cap) {
    lst[ptr] = Edge(y, beg[x], cap);
    beg[x] = ptr++;
    lst[ptr] = Edge(x, beg[y], 0);
    beg[y] = ptr++;
  }
  inline void addUndirectedEdge(const int x, const int y,
                                const CapacityType cap) {
    lst[ptr] = Edge(y, beg[x], cap);
    beg[x] = ptr++;
    lst[ptr] = Edge(x, beg[y], cap);
    beg[y] = ptr++;
  }
  CapacityType getMaxFlow(const int src, const int dst) {
    CapacityType aux, ans = 0;
    while (bfs(src, dst)) {
      copy(beg.begin(), beg.end(), adj.begin());
      do {
        aux = dfs(src, dst, INF);
        ans += aux;
      } while (cmp(aux));
    }
    return ans;
  }
  CapacityType getMinCut(const int src, const int dst, std::vector<int> &ans) {
    std::fill(oki.begin(), oki.end(), false);
    CapacityType sol = getMaxFlow(src, dst);
    fill(src);
    ans.clear();
    for (int i = 0; i < oki.size(); ++i)
      if (oki[i]) ans.push_back(i);
    return sol;
  }
};
struct edge {
  int x, y, a, b, c, d;
} edl[MMAX];
inline double sign(double x) {
  if (-EPS < x and x < +EPS) return 0;
  return x < 0 ? -1 : 1;
}
double check(double t, int n, int m) {
  int src = n + 1, dst = n + 2;
  double sum = 0;
  MaxFlow<double> myNetwork(n + 5, m * 6 + 5);
  for (int i = 1; i <= m; ++i) {
    int x = edl[i].x, y = edl[i].y;
    double le = t * edl[i].a + edl[i].b, ri = t * edl[i].c + edl[i].d;
    sum += le;
    myNetwork.addDirectedEdge(x, y, ri - le);
    myNetwork.addDirectedEdge(src, y, le);
    myNetwork.addDirectedEdge(x, dst, le);
  }
  return sum - myNetwork.getMaxFlow(src, dst);
}
double solve(double le, double ri, int n, int m) {
  double ans = 0;
  for (int i = 1; i <= 50; ++i) {
    double md = (le + ri) / 2.0;
    if (sign(check(md, n, m)) <= 0) {
      ans += fabs(md - le);
      le = md;
    } else
      ri = md;
  }
  return ans;
}
void debug(void) {
  MaxFlow<double> myNetwork(4, 6);
  myNetwork.addDirectedEdge(1, 2, 0.5);
  myNetwork.addDirectedEdge(2, 3, 0.3);
  cerr << myNetwork.getMaxFlow(1, 3);
  exit(0);
}
int main(void) {
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    cin >> edl[i].x >> edl[i].y;
    cin >> edl[i].a >> edl[i].b >> edl[i].c >> edl[i].d;
  }
  double le = 0.0, ri = 1.0;
  for (int i = 1; i <= 50; ++i) {
    double md1 = le + (ri - le) / 3.0, md2 = ri - (ri - le) / 3.0;
    double ans1 = check(md1, n, m), ans2 = check(md2, n, m);
    if (sign(ans1) <= 0 and sign(ans2) <= 0) {
      cout << setprecision(10) << fixed;
      cout << solve((md1 + md2) / 2.0, 1.0, n, m) +
                  solve((md1 + md2) / 2.0, 0.0, n, m);
      exit(0);
    }
    if (ans1 < ans2)
      ri = md2;
    else
      le = md1;
  }
  cout << setprecision(10) << fixed << 0.0;
  return 0;
}