#include <bits/stdc++.h>
long long ceil_d(long long a, long long b) {
  if (a <= 0) return a / b;
  return (a - 1) / b + 1;
}
long long floor_d(long long a, long long b) {
  if (a < 0) return (a + 1) / b - 1;
  return a / b;
}
int a1, b1, a2, b2;
long long l, r;
int eu(int a, int b, int &x, int &y) {
  bool s = false;
  if (a < b) {
    std::swap(a, b);
    s = true;
  }
  if (!b) {
    x = !s;
    y = s;
    return a;
  }
  int g = eu(a % b, b, x, y);
  y -= (a / b) * x;
  if (s) std::swap(x, y);
  return g;
}
void border(int k, long long b, long long ly, long long ry, long long &lx,
            long long &rx) {
  lx = ceil_d((long long)ly - b, k);
  rx = floor_d((long long)ry - b, k);
}
int main() {
  scanf("%d%d%d%d%lld%lld", &a1, &b1, &a2, &b2, &l, &r);
  int x0, y0, g;
  g = eu(a1, a2, x0, y0);
  if (((long long)b2 - b1) % g) {
    printf("0\n");
    return 0;
  }
  y0 *= -1;
  long long x = ((long long)b2 - b1) / g * x0,
            y = ((long long)b2 - b1) / g * y0;
  long long x1l, x1r, x2l, x2r;
  border(a1, b1, l, r, x1l, x1r);
  border(a2, b2, l, r, x2l, x2r);
  x1l = std::max(x1l, (long long)0);
  x2l = std::max(x2l, (long long)0);
  border(a2 / g, x, x1l, x1r, l, r);
  border(a1 / g, y, x2l, x2r, x1l, x1r);
  printf("%lld\n",
         std::max((long long)0, std::min(r, x1r) - std::max(l, x1l) + 1));
  return 0;
}

### Prompt

Please provide a cpp coded solution to the problem described below:

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 ceil_d(long long a, long long b) {
  if (a <= 0) return a / b;
  return (a - 1) / b + 1;
}
long long floor_d(long long a, long long b) {
  if (a < 0) return (a + 1) / b - 1;
  return a / b;
}
int a1, b1, a2, b2;
long long l, r;
int eu(int a, int b, int &x, int &y) {
  bool s = false;
  if (a < b) {
    std::swap(a, b);
    s = true;
  }
  if (!b) {
    x = !s;
    y = s;
    return a;
  }
  int g = eu(a % b, b, x, y);
  y -= (a / b) * x;
  if (s) std::swap(x, y);
  return g;
}
void border(int k, long long b, long long ly, long long ry, long long &lx,
            long long &rx) {
  lx = ceil_d((long long)ly - b, k);
  rx = floor_d((long long)ry - b, k);
}
int main() {
  scanf("%d%d%d%d%lld%lld", &a1, &b1, &a2, &b2, &l, &r);
  int x0, y0, g;
  g = eu(a1, a2, x0, y0);
  if (((long long)b2 - b1) % g) {
    printf("0\n");
    return 0;
  }
  y0 *= -1;
  long long x = ((long long)b2 - b1) / g * x0,
            y = ((long long)b2 - b1) / g * y0;
  long long x1l, x1r, x2l, x2r;
  border(a1, b1, l, r, x1l, x1r);
  border(a2, b2, l, r, x2l, x2r);
  x1l = std::max(x1l, (long long)0);
  x2l = std::max(x2l, (long long)0);
  border(a2 / g, x, x1l, x1r, l, r);
  border(a1 / g, y, x2l, x2r, x1l, x1r);
  printf("%lld\n",
         std::max((long long)0, std::min(r, x1r) - std::max(l, x1l) + 1));
  return 0;
}

```