#include <bits/stdc++.h>
using namespace std;
using llint = long long;
void gcd_ext(llint a, llint b, llint &m, llint &n, llint &g) {
  llint m0 = 1, n0 = 0, m1 = 0, n1 = 1;
  while (b != 0) {
    llint k, r;
    tie(k, r) = make_pair(a / b, a % b);
    a = b;
    b = r;
    if (b == 0) {
      break;
    }
    tie(m0, m1) = make_pair(m1, m0 - k * m1);
    tie(n0, n1) = make_pair(n1, n0 - k * n1);
  }
  tie(m, n, g) = make_tuple(m1, n1, a);
}
llint gcd(llint a, llint b) {
  llint m, n, g;
  gcd_ext(a, b, m, n, g);
  return g;
}
struct Solution {
  bool exists;
  llint x0, y0;
  llint dx, dy;
};
ostream &operator<<(ostream &os, const Solution &sol) {
  if (!sol.exists) {
    os << "[No solution]";
  } else {
    os << "Solution:\n";
    os << "{ x = " << sol.x0 << " + k*(" << sol.dx << ")\n";
    os << "{ y = " << sol.y0 << " + k*(" << sol.dy << ")\n";
  }
  return os;
}
Solution solve(llint u, llint v, llint c) {
  llint gu, gv, g;
  gcd_ext(u, v, gu, gv, g);
  if (c % g != 0) {
    return {false};
  }
  llint x0 = llint(c) * gu / g;
  llint y0 = llint(c) * gv / g;
  llint dx = -v / g;
  llint dy = u / g;
  return {true, x0, y0, dx, dy};
}
llint sign(llint x) {
  if (x == 0) return 0;
  if (x < 0) return -1;
  return 1;
}
llint divup(llint a, llint b) {
  int s = sign(a) * sign(b);
  a = abs(a);
  b = abs(b);
  if (a % b == 0) {
    return s * (a / b);
  }
  if (s < 0) {
    return -a / b;
  }
  return a / b + 1;
}
llint divdown(llint a, llint b) {
  int s = sign(a) * sign(b);
  a = abs(a);
  b = abs(b);
  if (a % b == 0) {
    return s * (a / b);
  }
  if (s < 0) {
    return -a / b - 1;
  }
  return a / b;
}
using ld = long double;
const ld kInfinity = std::numeric_limits<ld>::max();
int main() {
  llint a1, b1, a2, b2, L, R;
  cin >> a1 >> b1 >> a2 >> b2 >> L >> R;
  Solution sol = solve(a1, -a2, b2 - b1);
  if (!sol.exists) {
    cout << 0 << endl;
    return 0;
  }
  ld left_bord = -kInfinity;
  ld right_bord = kInfinity;
  llint den = a1 * sol.dx;
  if (sol.dx > 0) {
    left_bord = std::max<ld>(left_bord, divup(-sol.x0, sol.dx));
    left_bord = std::max(left_bord, ld(L - b1) / den - ld(sol.x0) / sol.dx);
    right_bord = std::min(right_bord, ld(R - b1) / den - ld(sol.x0) / sol.dx);
  } else {
    right_bord = std::min<ld>(right_bord, divdown(-sol.x0, sol.dx));
    right_bord = std::min(right_bord, ld(L - b1) / den - ld(sol.x0) / sol.dx);
    left_bord = std::max(left_bord, ld(R - b1) / den - ld(sol.x0) / sol.dx);
  }
  if (sol.dy > 0) {
    left_bord = std::max<ld>(left_bord, divup(-sol.y0, sol.dy));
  } else {
    right_bord = std::min<ld>(right_bord, divdown(-sol.y0, sol.dy));
  }
  llint left = ceil(left_bord);
  llint right = floor(right_bord);
  llint ans;
  if (left > right) {
    ans = 0;
  } else {
    ans = right - left + 1;
  }
  cout << ans << endl;
  return 0;
}

### Prompt

Generate a CPP solution to the following problem:

You are given two arithmetic progressions: a1k + b1 and a2l + b2. Find the number of integers x such that L ≤ x ≤ R and x = a1k' + b1 = a2l' + b2, for some integers k', l' ≥ 0.

Input

The only line contains six integers a1, b1, a2, b2, L, R (0 < a1, a2 ≤ 2·109, - 2·109 ≤ b1, b2, L, R ≤ 2·109, L ≤ R).

Output

Print the desired number of integers x.

Examples

Input

2 0 3 3 5 21


Output

3


Input

2 4 3 0 6 17


Output

2

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
using llint = long long;
void gcd_ext(llint a, llint b, llint &m, llint &n, llint &g) {
  llint m0 = 1, n0 = 0, m1 = 0, n1 = 1;
  while (b != 0) {
    llint k, r;
    tie(k, r) = make_pair(a / b, a % b);
    a = b;
    b = r;
    if (b == 0) {
      break;
    }
    tie(m0, m1) = make_pair(m1, m0 - k * m1);
    tie(n0, n1) = make_pair(n1, n0 - k * n1);
  }
  tie(m, n, g) = make_tuple(m1, n1, a);
}
llint gcd(llint a, llint b) {
  llint m, n, g;
  gcd_ext(a, b, m, n, g);
  return g;
}
struct Solution {
  bool exists;
  llint x0, y0;
  llint dx, dy;
};
ostream &operator<<(ostream &os, const Solution &sol) {
  if (!sol.exists) {
    os << "[No solution]";
  } else {
    os << "Solution:\n";
    os << "{ x = " << sol.x0 << " + k*(" << sol.dx << ")\n";
    os << "{ y = " << sol.y0 << " + k*(" << sol.dy << ")\n";
  }
  return os;
}
Solution solve(llint u, llint v, llint c) {
  llint gu, gv, g;
  gcd_ext(u, v, gu, gv, g);
  if (c % g != 0) {
    return {false};
  }
  llint x0 = llint(c) * gu / g;
  llint y0 = llint(c) * gv / g;
  llint dx = -v / g;
  llint dy = u / g;
  return {true, x0, y0, dx, dy};
}
llint sign(llint x) {
  if (x == 0) return 0;
  if (x < 0) return -1;
  return 1;
}
llint divup(llint a, llint b) {
  int s = sign(a) * sign(b);
  a = abs(a);
  b = abs(b);
  if (a % b == 0) {
    return s * (a / b);
  }
  if (s < 0) {
    return -a / b;
  }
  return a / b + 1;
}
llint divdown(llint a, llint b) {
  int s = sign(a) * sign(b);
  a = abs(a);
  b = abs(b);
  if (a % b == 0) {
    return s * (a / b);
  }
  if (s < 0) {
    return -a / b - 1;
  }
  return a / b;
}
using ld = long double;
const ld kInfinity = std::numeric_limits<ld>::max();
int main() {
  llint a1, b1, a2, b2, L, R;
  cin >> a1 >> b1 >> a2 >> b2 >> L >> R;
  Solution sol = solve(a1, -a2, b2 - b1);
  if (!sol.exists) {
    cout << 0 << endl;
    return 0;
  }
  ld left_bord = -kInfinity;
  ld right_bord = kInfinity;
  llint den = a1 * sol.dx;
  if (sol.dx > 0) {
    left_bord = std::max<ld>(left_bord, divup(-sol.x0, sol.dx));
    left_bord = std::max(left_bord, ld(L - b1) / den - ld(sol.x0) / sol.dx);
    right_bord = std::min(right_bord, ld(R - b1) / den - ld(sol.x0) / sol.dx);
  } else {
    right_bord = std::min<ld>(right_bord, divdown(-sol.x0, sol.dx));
    right_bord = std::min(right_bord, ld(L - b1) / den - ld(sol.x0) / sol.dx);
    left_bord = std::max(left_bord, ld(R - b1) / den - ld(sol.x0) / sol.dx);
  }
  if (sol.dy > 0) {
    left_bord = std::max<ld>(left_bord, divup(-sol.y0, sol.dy));
  } else {
    right_bord = std::min<ld>(right_bord, divdown(-sol.y0, sol.dy));
  }
  llint left = ceil(left_bord);
  llint right = floor(right_bord);
  llint ans;
  if (left > right) {
    ans = 0;
  } else {
    ans = right - left + 1;
  }
  cout << ans << endl;
  return 0;
}

```