#include <bits/stdc++.h>
long long a, k1, lowerX, upperX, x, xstep;
long long b, k2, lowerY, upperY, y, ystep;
long long l, r, d, D;
long long egcd(long long a, long long b, long long &x0, long long &y0) {
  x0 = 1, y0 = 0;
  long long x1 = 0, y1 = 1, q;
  while (b) {
    q = a / b;
    a = a - q * b;
    std::swap(a, b);
    x0 = x0 - q * x1;
    std::swap(x0, x1);
    y0 = y0 - q * y1;
    std::swap(y0, y1);
  }
  return a;
}
int sgn(long long a) { return a < 0 ? -1 : a > 0 ? 1 : 0; }
bool valid(long long x, long long y) {
  if (x < lowerX || x > upperX) return false;
  if (y < lowerY || y > upperY) return false;
  return true;
}
int main() {
  scanf("%lld%lld%lld%lld%lld%lld", &a, &k1, &b, &k2, &l, &r);
  if (k2 < k1) {
    std::swap(k2, k1);
    std::swap(a, b);
  }
  lowerX = std::max(0LL, ((l - k1) + (a - 1)) / a);
  upperX = (r - k1) < 0 ? -1 : (r - k1) / a;
  lowerY = std::max(0LL, ((l - k2) + (b - 1)) / b);
  upperY = (r - k2) < 0 ? -1 : (r - k2) / b;
  D = k2 - k1;
  d = egcd(a, -b, x, y);
  if (D % d) {
    printf("0\n");
    return 0;
  }
  x *= D / d;
  y *= D / d;
  xstep = -b / d;
  ystep = a / d;
  if (x < lowerX) {
    long long up = (lowerX - x + std::abs(xstep) - 1) / std::abs(xstep);
    if (xstep > 0)
      x += xstep * up, y -= ystep * up;
    else
      x -= xstep * up, y += ystep * up;
  }
  if (x > lowerX) {
    long long drop = (x - std::abs(lowerX)) / std::abs(xstep);
    if (xstep > 0)
      x -= xstep * drop, y += ystep * drop;
    else
      x += xstep * drop, y -= ystep * drop;
  }
  if (y < lowerY) {
    long long up = (lowerY - y + std::abs(ystep) - 1) / std::abs(ystep);
    if (ystep < 0)
      x += xstep * up, y -= ystep * up;
    else
      x -= xstep * up, y += ystep * up;
  }
  long long up1 = (upperX - x) / std::abs(xstep);
  long long up2;
  if (sgn(xstep) != sgn(ystep))
    up2 = (upperY - y) / std::abs(ystep);
  else {
    assert(false);
    up2 = (y - lowerY) / std::abs(ystep);
  }
  printf("%lld\n", std::max(0LL, std::min(up1, up2)) + valid(x, y));
  return 0;
}

### Prompt

In cpp, your task is to solve 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 a, k1, lowerX, upperX, x, xstep;
long long b, k2, lowerY, upperY, y, ystep;
long long l, r, d, D;
long long egcd(long long a, long long b, long long &x0, long long &y0) {
  x0 = 1, y0 = 0;
  long long x1 = 0, y1 = 1, q;
  while (b) {
    q = a / b;
    a = a - q * b;
    std::swap(a, b);
    x0 = x0 - q * x1;
    std::swap(x0, x1);
    y0 = y0 - q * y1;
    std::swap(y0, y1);
  }
  return a;
}
int sgn(long long a) { return a < 0 ? -1 : a > 0 ? 1 : 0; }
bool valid(long long x, long long y) {
  if (x < lowerX || x > upperX) return false;
  if (y < lowerY || y > upperY) return false;
  return true;
}
int main() {
  scanf("%lld%lld%lld%lld%lld%lld", &a, &k1, &b, &k2, &l, &r);
  if (k2 < k1) {
    std::swap(k2, k1);
    std::swap(a, b);
  }
  lowerX = std::max(0LL, ((l - k1) + (a - 1)) / a);
  upperX = (r - k1) < 0 ? -1 : (r - k1) / a;
  lowerY = std::max(0LL, ((l - k2) + (b - 1)) / b);
  upperY = (r - k2) < 0 ? -1 : (r - k2) / b;
  D = k2 - k1;
  d = egcd(a, -b, x, y);
  if (D % d) {
    printf("0\n");
    return 0;
  }
  x *= D / d;
  y *= D / d;
  xstep = -b / d;
  ystep = a / d;
  if (x < lowerX) {
    long long up = (lowerX - x + std::abs(xstep) - 1) / std::abs(xstep);
    if (xstep > 0)
      x += xstep * up, y -= ystep * up;
    else
      x -= xstep * up, y += ystep * up;
  }
  if (x > lowerX) {
    long long drop = (x - std::abs(lowerX)) / std::abs(xstep);
    if (xstep > 0)
      x -= xstep * drop, y += ystep * drop;
    else
      x += xstep * drop, y -= ystep * drop;
  }
  if (y < lowerY) {
    long long up = (lowerY - y + std::abs(ystep) - 1) / std::abs(ystep);
    if (ystep < 0)
      x += xstep * up, y -= ystep * up;
    else
      x -= xstep * up, y += ystep * up;
  }
  long long up1 = (upperX - x) / std::abs(xstep);
  long long up2;
  if (sgn(xstep) != sgn(ystep))
    up2 = (upperY - y) / std::abs(ystep);
  else {
    assert(false);
    up2 = (y - lowerY) / std::abs(ystep);
  }
  printf("%lld\n", std::max(0LL, std::min(up1, up2)) + valid(x, y));
  return 0;
}

```