#include <bits/stdc++.h>
long long dx[4] = {0, -1, 0, 1};
long long dy[4] = {1, 0, -1, 0};
using namespace std;
class pa3 {
 public:
  long long x, y, z;
  pa3(long long x = 0, long long y = 0, long long z = 0) : x(x), y(y), z(z) {}
  bool operator<(const pa3 &p) const {
    if (x != p.x) return x < p.x;
    if (y != p.y) return y < p.y;
    return z < p.z;
  }
  bool operator>(const pa3 &p) const {
    if (x != p.x) return x > p.x;
    if (y != p.y) return y > p.y;
    return z > p.z;
  }
  bool operator==(const pa3 &p) const {
    return x == p.x && y == p.y && z == p.z;
  }
  bool operator!=(const pa3 &p) const {
    return !(x == p.x && y == p.y && z == p.z);
  }
};
class pa4 {
 public:
  long long x;
  long long y, z, w;
  pa4(long long x = 0, long long y = 0, long long z = 0, long long w = 0)
      : x(x), y(y), z(z), w(w) {}
  bool operator<(const pa4 &p) const {
    if (x != p.x) return x < p.x;
    if (y != p.y) return y < p.y;
    if (z != p.z) return z < p.z;
    return w < p.w;
  }
  bool operator>(const pa4 &p) const {
    if (x != p.x) return x > p.x;
    if (y != p.y) return y > p.y;
    if (z != p.z) return z > p.z;
    return w > p.w;
  }
  bool operator==(const pa4 &p) const {
    return x == p.x && y == p.y && z == p.z && w == p.w;
  }
  bool operator!=(const pa4 &p) const {
    return !(x == p.x && y == p.y && z == p.z && w == p.w);
  }
};
class pa2 {
 public:
  long long x, y;
  pa2(long long x = 0, long long y = 0) : x(x), y(y) {}
  pa2 operator+(pa2 p) { return pa2(x + p.x, y + p.y); }
  pa2 operator-(pa2 p) { return pa2(x - p.x, y - p.y); }
  bool operator<(const pa2 &p) const { return x != p.x ? x < p.x : y < p.y; }
  bool operator>(const pa2 &p) const { return x != p.x ? x > p.x : y > p.y; }
  bool operator==(const pa2 &p) const {
    return abs(x - p.x) == 0 && abs(y - p.y) == 0;
  }
  bool operator!=(const pa2 &p) const {
    return !(abs(x - p.x) == 0 && abs(y - p.y) == 0);
  }
};
class Point {
 public:
  double x, y;
  Point(double x = 0, double y = 0) : x(x), y(y) {}
  Point operator+(Point p) { return Point(x + p.x, y + p.y); }
  Point operator-(Point p) { return Point(x - p.x, y - p.y); }
  Point operator*(double a) { return Point(x * a, y * a); }
  Point operator/(double a) { return Point(x / a, y / a); }
  double absv() { return sqrt(norm()); }
  double norm() { return x * x + y * y; }
  bool operator<(const Point &p) const { return x != p.x ? x < p.x : y < p.y; }
  bool operator==(const Point &p) const {
    return fabs(x - p.x) < (1e-10) && fabs(y - p.y) < (1e-10);
  }
};
struct Segment {
  Point p1, p2;
};
double dot(Point a, Point b) { return a.x * b.x + a.y * b.y; }
double cross(Point a, Point b) { return a.x * b.y - a.y * b.x; }
bool parareru(Point a, Point b, Point c, Point d) {
  return abs(cross(a - b, d - c)) < (1e-10);
}
double distance_ls_p(Point a, Point b, Point c) {
  if (dot(b - a, c - a) < (1e-10)) return (c - a).absv();
  if (dot(a - b, c - b) < (1e-10)) return (c - b).absv();
  return abs(cross(b - a, c - a)) / (b - a).absv();
}
bool is_intersected_ls(Segment a, Segment b) {
  if (a.p1 == b.p1 || a.p2 == b.p1 || a.p1 == b.p2 || a.p2 == b.p2)
    return false;
  if (parareru((a.p2), (a.p1), (a.p1), (b.p2)) &&
      parareru((a.p2), (a.p1), (a.p1), (b.p1))) {
    if (dot(a.p1 - b.p1, a.p1 - b.p2) < (1e-10)) return true;
    if (dot(a.p2 - b.p1, a.p2 - b.p2) < (1e-10)) return true;
    if (dot(a.p1 - b.p1, a.p2 - b.p1) < (1e-10)) return true;
    if (dot(a.p1 - b.p2, a.p2 - b.p2) < (1e-10)) return true;
    return false;
  } else
    return (cross(a.p2 - a.p1, b.p1 - a.p1) * cross(a.p2 - a.p1, b.p2 - a.p1) <
            (1e-10)) &&
           (cross(b.p2 - b.p1, a.p1 - b.p1) * cross(b.p2 - b.p1, a.p2 - b.p1) <
            (1e-10));
}
double segment_dis(Segment a, Segment b) {
  if (is_intersected_ls(a, b)) return 0;
  double r = distance_ls_p(a.p1, a.p2, b.p1);
  r = min(r, distance_ls_p(a.p1, a.p2, b.p2));
  r = min(r, distance_ls_p(b.p1, b.p2, a.p2));
  r = min(r, distance_ls_p(b.p1, b.p2, a.p1));
  return r;
}
Point intersection_ls(Segment a, Segment b) {
  Point ba = b.p2 - b.p1;
  double d1 = abs(cross(ba, a.p1 - b.p1));
  double d2 = abs(cross(ba, a.p2 - b.p1));
  double t = d1 / (d1 + d2);
  return a.p1 + (a.p2 - a.p1) * t;
}
string itos(long long i) {
  ostringstream s;
  s << i;
  return s.str();
}
long long gcd(long long v, long long b) {
  if (v > b) return gcd(b, v);
  if (v == b) return b;
  if (b % v == 0) return v;
  return gcd(v, b % v);
}
double distans(double x1, double y1, double x2, double y2) {
  double rr = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
  return sqrt(rr);
}
long long mod;
long long pr[401000];
long long inv[401000];
long long beki(long long wa, long long rr, long long warukazu) {
  if (rr == 0) return 1 % warukazu;
  if (rr == 1) return wa % warukazu;
  if (rr % 2 == 1) return (beki(wa, rr - 1, warukazu) * wa) % warukazu;
  long long zx = beki(wa, rr / 2, warukazu);
  return (zx * zx) % warukazu;
}
long long comb(long long nn, long long rr) {
  long long r = pr[nn] * inv[rr];
  r %= mod;
  r *= inv[nn - rr];
  r %= mod;
  return r;
}
void gya(long long ert) {
  pr[0] = 1;
  for (long long i = 1; i < ert; i++) {
    pr[i] = (pr[i - 1] * i) % mod;
  }
  for (long long i = 0; i < ert; i++) inv[i] = beki(pr[i], mod - 2, mod);
}
void extgcd(long long a, long long b, long long *x, long long *y,
            long long *d) {
  long long u, v, q, tmp;
  *x = 1;
  *y = 0;
  u = 0;
  v = 1;
  while (b > 0) {
    q = a / b;
    tmp = u;
    u = *x - q * u;
    *x = tmp;
    tmp = v;
    v = *y - q * v;
    *y = tmp;
    tmp = b;
    b = a - q * b;
    a = tmp;
  }
  *d = a;
}
long long ko(long long l, long long r, long long bai) {
  if (l > r) return 0;
  if (l > 0) {
    return r / bai - (l - 1) / bai;
  }
  if (r < 0) {
    l *= -1;
    r *= -1;
    swap(l, r);
    return r / bai - (l - 1) / bai;
  }
  return 1 + ko(1, r, bai) + ko(l, -1, bai);
}
signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  long long a1, b2, a2, b1, l, r;
  cin >> a1 >> b1 >> a2 >> b2 >> l >> r;
  long long B = b2 - b1;
  long long lcm = (a1 / gcd(a1, a2)) * a2;
  if (B == 0) {
    l -= b1;
    r -= b1;
    if (r < 0)
      cout << 0 << endl;
    else {
      l = max(l, 0ll);
      if (l == 0)
        cout << r / lcm + 1 << endl;
      else
        cout << r / lcm - (l - 1) / lcm << endl;
    }
    return 0;
  }
  long long g = gcd(a1, a2);
  if (abs(B) % g) {
    cout << 0 << endl;
    return 0;
  }
  long long x, y, z;
  extgcd(a1, +a2, &x, &y, &z);
  y *= -1;
  long long sa = B / z;
  x *= sa;
  y *= sa;
  long long d1 = a2 / g;
  long long d2 = a1 / g;
  if (x < 0) {
    long long nokori = -x;
    long long kai = nokori / d1 + !!(nokori % d1);
    x += d1 * kai;
    y += d2 * kai;
  }
  if (y < 0) {
    long long nokori = -y;
    long long kai = nokori / d2 + !!(nokori % d2);
    x += d1 * kai;
    y += d2 * kai;
  }
  if (x < 0 || y < 0) exit(1);
  {
    long long e1 = x / d1, e2 = y / d2;
    long long e3 = min(e1, e2);
    x -= e3 * d1;
    y -= e3 * d2;
  }
  if (x < 0 || y < 0) exit(1);
  long long dd = a1 * x + b1;
  dd = a2 * y + b2;
  l -= dd, r -= dd;
  {
    if (r < 0)
      cout << 0 << endl;
    else {
      l = max(l, 0ll);
      if (l == 0)
        cout << r / lcm + 1 << endl;
      else
        cout << r / lcm - (l - 1) / lcm << endl;
    }
    return 0;
  }
  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>
long long dx[4] = {0, -1, 0, 1};
long long dy[4] = {1, 0, -1, 0};
using namespace std;
class pa3 {
 public:
  long long x, y, z;
  pa3(long long x = 0, long long y = 0, long long z = 0) : x(x), y(y), z(z) {}
  bool operator<(const pa3 &p) const {
    if (x != p.x) return x < p.x;
    if (y != p.y) return y < p.y;
    return z < p.z;
  }
  bool operator>(const pa3 &p) const {
    if (x != p.x) return x > p.x;
    if (y != p.y) return y > p.y;
    return z > p.z;
  }
  bool operator==(const pa3 &p) const {
    return x == p.x && y == p.y && z == p.z;
  }
  bool operator!=(const pa3 &p) const {
    return !(x == p.x && y == p.y && z == p.z);
  }
};
class pa4 {
 public:
  long long x;
  long long y, z, w;
  pa4(long long x = 0, long long y = 0, long long z = 0, long long w = 0)
      : x(x), y(y), z(z), w(w) {}
  bool operator<(const pa4 &p) const {
    if (x != p.x) return x < p.x;
    if (y != p.y) return y < p.y;
    if (z != p.z) return z < p.z;
    return w < p.w;
  }
  bool operator>(const pa4 &p) const {
    if (x != p.x) return x > p.x;
    if (y != p.y) return y > p.y;
    if (z != p.z) return z > p.z;
    return w > p.w;
  }
  bool operator==(const pa4 &p) const {
    return x == p.x && y == p.y && z == p.z && w == p.w;
  }
  bool operator!=(const pa4 &p) const {
    return !(x == p.x && y == p.y && z == p.z && w == p.w);
  }
};
class pa2 {
 public:
  long long x, y;
  pa2(long long x = 0, long long y = 0) : x(x), y(y) {}
  pa2 operator+(pa2 p) { return pa2(x + p.x, y + p.y); }
  pa2 operator-(pa2 p) { return pa2(x - p.x, y - p.y); }
  bool operator<(const pa2 &p) const { return x != p.x ? x < p.x : y < p.y; }
  bool operator>(const pa2 &p) const { return x != p.x ? x > p.x : y > p.y; }
  bool operator==(const pa2 &p) const {
    return abs(x - p.x) == 0 && abs(y - p.y) == 0;
  }
  bool operator!=(const pa2 &p) const {
    return !(abs(x - p.x) == 0 && abs(y - p.y) == 0);
  }
};
class Point {
 public:
  double x, y;
  Point(double x = 0, double y = 0) : x(x), y(y) {}
  Point operator+(Point p) { return Point(x + p.x, y + p.y); }
  Point operator-(Point p) { return Point(x - p.x, y - p.y); }
  Point operator*(double a) { return Point(x * a, y * a); }
  Point operator/(double a) { return Point(x / a, y / a); }
  double absv() { return sqrt(norm()); }
  double norm() { return x * x + y * y; }
  bool operator<(const Point &p) const { return x != p.x ? x < p.x : y < p.y; }
  bool operator==(const Point &p) const {
    return fabs(x - p.x) < (1e-10) && fabs(y - p.y) < (1e-10);
  }
};
struct Segment {
  Point p1, p2;
};
double dot(Point a, Point b) { return a.x * b.x + a.y * b.y; }
double cross(Point a, Point b) { return a.x * b.y - a.y * b.x; }
bool parareru(Point a, Point b, Point c, Point d) {
  return abs(cross(a - b, d - c)) < (1e-10);
}
double distance_ls_p(Point a, Point b, Point c) {
  if (dot(b - a, c - a) < (1e-10)) return (c - a).absv();
  if (dot(a - b, c - b) < (1e-10)) return (c - b).absv();
  return abs(cross(b - a, c - a)) / (b - a).absv();
}
bool is_intersected_ls(Segment a, Segment b) {
  if (a.p1 == b.p1 || a.p2 == b.p1 || a.p1 == b.p2 || a.p2 == b.p2)
    return false;
  if (parareru((a.p2), (a.p1), (a.p1), (b.p2)) &&
      parareru((a.p2), (a.p1), (a.p1), (b.p1))) {
    if (dot(a.p1 - b.p1, a.p1 - b.p2) < (1e-10)) return true;
    if (dot(a.p2 - b.p1, a.p2 - b.p2) < (1e-10)) return true;
    if (dot(a.p1 - b.p1, a.p2 - b.p1) < (1e-10)) return true;
    if (dot(a.p1 - b.p2, a.p2 - b.p2) < (1e-10)) return true;
    return false;
  } else
    return (cross(a.p2 - a.p1, b.p1 - a.p1) * cross(a.p2 - a.p1, b.p2 - a.p1) <
            (1e-10)) &&
           (cross(b.p2 - b.p1, a.p1 - b.p1) * cross(b.p2 - b.p1, a.p2 - b.p1) <
            (1e-10));
}
double segment_dis(Segment a, Segment b) {
  if (is_intersected_ls(a, b)) return 0;
  double r = distance_ls_p(a.p1, a.p2, b.p1);
  r = min(r, distance_ls_p(a.p1, a.p2, b.p2));
  r = min(r, distance_ls_p(b.p1, b.p2, a.p2));
  r = min(r, distance_ls_p(b.p1, b.p2, a.p1));
  return r;
}
Point intersection_ls(Segment a, Segment b) {
  Point ba = b.p2 - b.p1;
  double d1 = abs(cross(ba, a.p1 - b.p1));
  double d2 = abs(cross(ba, a.p2 - b.p1));
  double t = d1 / (d1 + d2);
  return a.p1 + (a.p2 - a.p1) * t;
}
string itos(long long i) {
  ostringstream s;
  s << i;
  return s.str();
}
long long gcd(long long v, long long b) {
  if (v > b) return gcd(b, v);
  if (v == b) return b;
  if (b % v == 0) return v;
  return gcd(v, b % v);
}
double distans(double x1, double y1, double x2, double y2) {
  double rr = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
  return sqrt(rr);
}
long long mod;
long long pr[401000];
long long inv[401000];
long long beki(long long wa, long long rr, long long warukazu) {
  if (rr == 0) return 1 % warukazu;
  if (rr == 1) return wa % warukazu;
  if (rr % 2 == 1) return (beki(wa, rr - 1, warukazu) * wa) % warukazu;
  long long zx = beki(wa, rr / 2, warukazu);
  return (zx * zx) % warukazu;
}
long long comb(long long nn, long long rr) {
  long long r = pr[nn] * inv[rr];
  r %= mod;
  r *= inv[nn - rr];
  r %= mod;
  return r;
}
void gya(long long ert) {
  pr[0] = 1;
  for (long long i = 1; i < ert; i++) {
    pr[i] = (pr[i - 1] * i) % mod;
  }
  for (long long i = 0; i < ert; i++) inv[i] = beki(pr[i], mod - 2, mod);
}
void extgcd(long long a, long long b, long long *x, long long *y,
            long long *d) {
  long long u, v, q, tmp;
  *x = 1;
  *y = 0;
  u = 0;
  v = 1;
  while (b > 0) {
    q = a / b;
    tmp = u;
    u = *x - q * u;
    *x = tmp;
    tmp = v;
    v = *y - q * v;
    *y = tmp;
    tmp = b;
    b = a - q * b;
    a = tmp;
  }
  *d = a;
}
long long ko(long long l, long long r, long long bai) {
  if (l > r) return 0;
  if (l > 0) {
    return r / bai - (l - 1) / bai;
  }
  if (r < 0) {
    l *= -1;
    r *= -1;
    swap(l, r);
    return r / bai - (l - 1) / bai;
  }
  return 1 + ko(1, r, bai) + ko(l, -1, bai);
}
signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  long long a1, b2, a2, b1, l, r;
  cin >> a1 >> b1 >> a2 >> b2 >> l >> r;
  long long B = b2 - b1;
  long long lcm = (a1 / gcd(a1, a2)) * a2;
  if (B == 0) {
    l -= b1;
    r -= b1;
    if (r < 0)
      cout << 0 << endl;
    else {
      l = max(l, 0ll);
      if (l == 0)
        cout << r / lcm + 1 << endl;
      else
        cout << r / lcm - (l - 1) / lcm << endl;
    }
    return 0;
  }
  long long g = gcd(a1, a2);
  if (abs(B) % g) {
    cout << 0 << endl;
    return 0;
  }
  long long x, y, z;
  extgcd(a1, +a2, &x, &y, &z);
  y *= -1;
  long long sa = B / z;
  x *= sa;
  y *= sa;
  long long d1 = a2 / g;
  long long d2 = a1 / g;
  if (x < 0) {
    long long nokori = -x;
    long long kai = nokori / d1 + !!(nokori % d1);
    x += d1 * kai;
    y += d2 * kai;
  }
  if (y < 0) {
    long long nokori = -y;
    long long kai = nokori / d2 + !!(nokori % d2);
    x += d1 * kai;
    y += d2 * kai;
  }
  if (x < 0 || y < 0) exit(1);
  {
    long long e1 = x / d1, e2 = y / d2;
    long long e3 = min(e1, e2);
    x -= e3 * d1;
    y -= e3 * d2;
  }
  if (x < 0 || y < 0) exit(1);
  long long dd = a1 * x + b1;
  dd = a2 * y + b2;
  l -= dd, r -= dd;
  {
    if (r < 0)
      cout << 0 << endl;
    else {
      l = max(l, 0ll);
      if (l == 0)
        cout << r / lcm + 1 << endl;
      else
        cout << r / lcm - (l - 1) / lcm << endl;
    }
    return 0;
  }
  return 0;
}

```