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 double dinf = 1e100;
template <typename T>
void pfill(T *pst, const T *ped, T val) {
  for (; pst != ped; *(pst++) = val)
    ;
}
template <typename T>
class Edge {
 public:
  int ed, nx;
  T r;
  Edge(int ed = 0, int nx = 0, T r = 0) : ed(ed), nx(nx), r(r) {}
};
template <typename T>
class MapManager {
 public:
  int *h;
  vector<Edge<T> > es;
  MapManager() {}
  MapManager(int n) {
    h = new int[(n + 1)];
    pfill(h, h + n + 1, -1);
  }
  ~MapManager() {
    delete[] h;
    es.clear();
  }
  void addEdge(int u, int v, T r) {
    es.push_back(Edge<T>(v, h[u], r));
    h[u] = (signed)es.size() - 1;
  }
  void addArc(int u, int v, T cap) {
    addEdge(u, v, cap);
    addEdge(v, u, 0);
  }
  Edge<T> &operator[](int p) { return es[p]; }
};
class Dcmp {
 public:
  const static double eps;
  bool operator()(double x) { return fabs(x) >= eps; }
} dcmp;
const double Dcmp ::eps = 5e-8;
template <typename Type>
class Network {
 public:
  int S, T;
  int *cur, *div;
  MapManager<Type> g;
  Network() {}
  Network(int S, int T) : S(S), T(T), g(T + 1) {
    cur = new int[(T + 1)];
    div = new int[(T + 1)];
  }
  ~Network() {
    delete[] cur;
    delete[] div;
  }
  bool bfs() {
    static queue<int> que;
    pfill(div, div + T + 1, -1);
    div[S] = 0;
    que.push(S);
    while (!que.empty()) {
      int e = que.front();
      que.pop();
      for (int i = g.h[e], eu; ~i; i = g[i].nx) {
        if (!dcmp(g[i].r)) continue;
        eu = g[i].ed;
        if (!~div[eu]) {
          div[eu] = div[e] + 1;
          que.push(eu);
        }
      }
    }
    return ~div[T];
  }
  Type dfs(int p, Type minf) {
    if (p == T || !dcmp(minf)) return minf;
    Type flow = 0, f;
    for (int &i = cur[p], e; (~i); i = cur[p], i = g[i].nx) {
      e = g[i].ed;
      if (div[e] == div[p] + 1 && dcmp(f = dfs(e, min(minf, g[i].r))) > 0) {
        flow += f;
        g[i].r -= f;
        g[i ^ 1].r += f;
        minf -= f;
        if (!dcmp(minf)) {
          break;
        }
      }
    }
    return flow;
  }
  Type dinic() {
    Type rt = 0;
    while (bfs()) {
      for (int i = 0; i <= T; i++) cur[i] = g.h[i];
      rt += dfs(S, dinf);
    }
    return rt;
  }
};
const int N = 1e3 + 5, M = 2e3 + 5;
int n, m;
Network<double> *network;
int us[M], vs[M], as[M], bs[M], cs[M], ds[M];
inline void init() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; i++) {
    scanf("%d%d%d%d%d%d", us + i, vs + i, as + i, bs + i, cs + i, ds + i);
  }
}
double in[N], out[N];
double build(double t) {
  MapManager<double> &g = network->g;
  for (int i = 1; i <= n; i++) {
    in[i] = out[i] = 0.0;
  }
  double rt = 0;
  for (int i = 0; i < m; i++) {
    double low = as[i] * t + bs[i], dif;
    g[i << 1].r = dif = (cs[i] - as[i]) * t + ds[i] - bs[i];
    g[i << 1 | 1].r = 0.0;
    out[us[i]] += low;
    in[vs[i]] += low;
    rt += low;
  }
  int s = (m << 1);
  for (int i = 0; i < n; i++, s += 2) {
    g[s].r = in[i + 1];
    g[s | 1].r = 0;
  }
  for (int i = 0; i < n; i++, s += 2) {
    g[s].r = out[i + 1];
    g[s | 1].r = 0;
  }
  return rt;
}
inline void solve() {
  network = new Network<double>(0, n + 1);
  MapManager<double> &g = network->g;
  for (int i = 0; i < m; i++) {
    g.addArc(us[i], vs[i], 0.0);
  }
  for (int i = 0; i < n; i++) {
    g.addArc(0, i + 1, 0.0);
  }
  for (int i = 0; i < n; i++) {
    g.addArc(i + 1, n + 1, 0.0);
  }
  double div_eps = 1e-7;
  double l = 0, r = 1 - div_eps, mid, f1, f2, low;
  for (int _ = 0; l + Dcmp ::eps < r && _ < 64; _++) {
    mid = (l + r) / 2;
    low = build(mid);
    f1 = low - network->dinic();
    low = build(mid + div_eps);
    f2 = low - network->dinic();
    if (!dcmp(f1 - f2)) {
      r = mid;
    } else if (f1 > f2) {
      l = mid;
    } else {
      r = mid;
    }
  }
  double L = r;
  l = L, r = 1 - div_eps;
  for (int _ = 0; l + Dcmp ::eps < r && _ < 64; _++) {
    mid = (l + r) / 2;
    low = build(mid);
    f1 = low - network->dinic();
    low = build(mid + div_eps);
    f2 = low - network->dinic();
    if (!dcmp(f1 - f2)) {
      l = mid;
    } else if (f1 > f2) {
      l = mid;
    } else {
      r = mid;
    }
  }
  low = build(L);
  f1 = low - network->dinic();
  if (dcmp(f1)) {
    puts("0.000000");
  } else {
    printf("%.7lf\n", l - L);
  }
}
int main() {
  init();
  solve();
  return 0;
}