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 N = 2e5;
const long long inf = 1e18;
vector<int> Eid[N];
int n, m, cnt, S, T, in[N], out[N], cur[N];
long long d[N];
struct Edge {
  long long c;
  int v;
} E[N];
void AddEdge(int x, int y, long long c) {
  E[cnt].v = y, E[cnt].c = c;
  Eid[x].push_back(cnt++);
  E[cnt].v = x, E[cnt].c = 0;
  Eid[y].push_back(cnt++);
}
bool BFS() {
  static int Q[N];
  int x, ql, qr;
  for (int i = 0; i <= T; i++) d[i] = -1;
  Q[ql = qr = 0] = S;
  d[S] = 0;
  while (ql <= qr) {
    x = Q[ql++];
    for (int i = 0; i < Eid[x].size(); i++) {
      const Edge &e = E[Eid[x][i]];
      if (e.c && d[e.v] == -1) {
        Q[++qr] = e.v;
        d[e.v] = d[x] + 1;
        if (e.v == T) return 1;
      }
    }
  }
  return 0;
}
long long Aug(int x, long long a) {
  if (x == T) return a;
  long long aug = 0, delta;
  for (int &i = cur[x]; i < Eid[x].size(); i++) {
    Edge &e = E[Eid[x][i]];
    if (e.c && d[e.v] == d[x] + 1) {
      delta = Aug(e.v, min(a, e.c));
      if (delta) {
        e.c -= delta;
        E[Eid[x][i] ^ 1].c += delta;
        aug += delta;
        if (!(a -= delta)) break;
      }
    }
  }
  if (!aug) d[x] = -1;
  return aug;
}
long long MaxFlow() {
  long long flow = 0;
  while (BFS()) {
    for (int i = 0; i <= T; i++) cur[i] = 0;
    flow += Aug(S, inf);
  }
  return flow;
}
int id[N];
int u[N], v[N];
long long A[N], B[N], C[N], D[N];
long long check(int t) {
  long long ans = 0;
  for (int i = 1; i <= m; ++i) {
    for (int j = id[i]; j < id[i] + 6; ++j) E[j].c = 0;
    long long l = A[i] * t + B[i];
    long long r = C[i] * t + D[i];
    E[id[i]].c = E[id[i] + 2].c = l;
    E[id[i] + 4].c = r - l;
    ans += l;
  }
  return ans - MaxFlow();
}
int main() {
  cin >> n >> m;
  T = n + 1;
  for (int i = 1; i <= m; ++i) {
    scanf("%d %d %I64d %I64d %I64d %I64d", u + i, v + i, A + i, B + i, C + i,
          D + i);
    B[i] *= 1e8;
    D[i] *= 1e8;
    id[i] = cnt;
    AddEdge(S, v[i], 0);
    AddEdge(u[i], T, 0);
    AddEdge(u[i], v[i], 0);
  }
  long long l1, r1, l = 0, r = 1e8, mid;
  while (r - l > 6) {
    l1 = (r - l) / 3 + l;
    r1 = r - (r - l) / 3;
    if (check(l1) <= check(r1))
      r = r1;
    else
      l = l1;
  }
  long long tmp = check(l1), tmp1;
  for (int i = l1; i <= r1; ++i) {
    tmp1 = check(i);
    if (tmp1 < tmp) {
      l1 = i;
      tmp = tmp1;
    }
  }
  if (tmp) return puts("0");
  l = l1;
  r = 1e8;
  while (l < r) {
    if (l + 1 == r) {
      if (check(r) == 0)
        l++;
      else
        r--;
      break;
    }
    mid = l + r >> 1;
    if (check(mid) == 0)
      l = mid;
    else
      r = mid;
  }
  printf("%.10f\n", (l - l1 + 1) / 1e8);
}