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;
template <class T>
struct flow_network {
  int n;
  vector<vector<int>> adj;
  struct edge {
    int from, to;
    T capacity, flow;
  };
  vector<edge> edges;
  T flow = 0;
  flow_network(int n) : n(n), adj(n) {}
  void clear_flow() {
    for (auto &e : edges) e.flow = 0;
    flow = 0;
  }
  int insert(int from, int to, T forward_cap, T backward_cap) {
    int ind = (int)edges.size();
    adj[from].push_back(ind);
    edges.push_back({from, to, forward_cap, 0});
    adj[to].push_back(ind + 1);
    edges.push_back({to, from, backward_cap, 0});
    return ind;
  }
  void add_flow(int i, T f) {
    edges[i].flow += f;
    edges[i ^ 1].flow -= f;
  }
};
template <class T>
struct dinic {
  static constexpr T eps = (T)1e-9, inf = numeric_limits<T>::max();
  flow_network<T> &g;
  dinic(flow_network<T> &g) : g(g), ptr(g.n), level(g.n), q(g.n) {}
  vector<int> ptr, level, q;
  int s = -1, t = -1;
  bool bfs() {
    fill(level.begin(), level.end(), -1);
    q[0] = t;
    level[t] = 0;
    int beg = 0, end = 1;
    while (beg < end) {
      int i = q[beg++];
      for (auto ind : g.adj[i]) {
        auto &e = g.edges[ind];
        auto &re = g.edges[ind ^ 1];
        if (re.capacity - re.flow > eps && level[e.to] == -1) {
          level[e.to] = level[i] + 1;
          if (e.to == s) return true;
          q[end++] = e.to;
        }
      }
    }
    return false;
  }
  T dfs(int u, T w) {
    if (u == t) return w;
    int &j = ptr[u];
    while (j >= 0) {
      int ind = g.adj[u][j];
      auto &e = g.edges[ind];
      if (e.capacity - e.flow > eps && level[e.to] == level[u] - 1) {
        T F = dfs(e.to, min(e.capacity - e.flow, w));
        if (F > eps) {
          g.add_flow(ind, F);
          return F;
        }
      }
      --j;
    }
    return 0;
  }
  T max_flow(int s, int t) {
    this->s = s, this->t = t;
    while (bfs()) {
      for (int i = 0; i < g.n; ++i) ptr[i] = (int)g.adj[i].size() - 1;
      T sum = 0;
      while (true) {
        T add = dfs(s, inf);
        if (add <= eps) break;
        sum += add;
      }
      if (sum <= eps) break;
      g.flow += sum;
    }
    return g.flow;
  }
  pair<T, vector<bool>> min_cut(int s, int t) {
    T cut = max_flow(s, t);
    vector<bool> res(g.n);
    for (int i = 0; i < g.n; ++i) res[i] = level[i] != -1;
    return {cut, res};
  }
};
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin.exceptions(ios::badbit | ios::failbit);
  int n, m;
  cin >> n >> m;
  flow_network<long long> F(n + 2);
  dinic<long long> D(F);
  int src = n, snk = n + 1;
  const int scale = 1e7;
  vector<array<int, 6>> edges(m);
  vector<array<int, 3>> ind(m);
  long long req = 0;
  for (auto i = 0; i < m; ++i) {
    for (auto j = 0; j < 6; ++j) {
      cin >> edges[i][j];
    }
    --edges[i][0], --edges[i][1];
    ind[i] = {F.insert(src, edges[i][1], 0, 0),
              F.insert(edges[i][0], edges[i][1], 0, 0),
              F.insert(edges[i][0], snk, 0, 0)};
  }
  auto gap = [&](int t) {
    F.clear_flow();
    long long lsum = 0;
    for (auto i = 0; i < m; ++i) {
      auto [u, v, a, b, c, d] = edges[i];
      F.edges[ind[i][0]].capacity = 1LL * t * a + 1LL * scale * b;
      F.edges[ind[i][1]].capacity = 1LL * t * (c - a) + 1LL * scale * (d - b);
      F.edges[ind[i][2]].capacity = 1LL * t * a + 1LL * scale * b;
      lsum += 1LL * t * a + 1LL * scale * b;
    }
    return lsum - D.max_flow(src, snk);
  };
  int low = 0, high = 1e7 + 1;
  while (high - low >= 2) {
    int mid = low + (high - low >> 1);
    if (gap(mid - 1) > gap(mid)) {
      low = mid;
    } else {
      high = mid;
    }
  }
  int l = low;
  if (gap(l)) {
    cout << "0\n";
    return 0;
  }
  low = l, high = 1e7 + 1;
  while (high - low >= 2) {
    int mid = low + (high - low >> 1);
    if (gap(mid)) {
      high = mid;
    } else {
      low = mid;
    }
  }
  int r = high;
  cout << fixed << setprecision(15);
  cout << 1.0 * (r - l) / scale << "\n";
  return 0;
}