#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b, long long &x, long long &y) {
  if (a == 0) {
    x = 0;
    y = 1;
    return b;
  }
  long long x1, y1;
  long long d = gcd(b % a, a, x1, y1);
  x = y1 - (b / a) * x1;
  y = x1;
  return d;
}
pair<long long, long long> find_any_solution(long long a, long long b,
                                             long long c, long long &x0,
                                             long long &y0, long long &g) {
  g = gcd(abs(a), abs(b), x0, y0);
  if (c % g) {
    return make_pair(-1000000000000000000, -1000000000000000000);
  }
  x0 *= c / g;
  y0 *= c / g;
  if (a < 0) x0 = -x0;
  if (b < 0) y0 = -y0;
  return make_pair(x0, y0);
}
void makeMin(long long &x, long long &y, long long k1, long long k2) {
  long long t = x / k1;
  x = x - (t * k1);
  y = y - (t * k2);
  if (x < 0) {
    x = x + k1;
    y = y + k2;
  }
  if (y < 0) {
    t = y / k2;
    x = x - (t * k1);
    y = y - (t * k2);
    if (y < 0) {
      x = x + k1;
      y = y + k2;
    }
  }
}
long long findNum(long long f, long long x, long long lc) {
  long long ans = x - f;
  if (ans < 0) return 0;
  ans = ans / lc;
  ans++;
  if (ans < 0) ans = 0;
  return ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long a1, b1, a2, b2, l, r;
  cin >> a1 >> b1 >> a2 >> b2 >> l >> r;
  long long a = a1;
  long long b = -a2;
  long long c = b2 - b1;
  long long x, y;
  long long g;
  pair<long long, long long> p = find_any_solution(a, b, c, x, y, g);
  if (p.first == -1000000000000000000)
    cout << 0 << endl;
  else {
    long long k1 = b / g;
    long long k2 = a / g;
    k1 = -k1;
    makeMin(p.first, p.second, k1, k2);
    long long f = a1 * p.first + b1;
    long long lc = a1 / g;
    lc = lc * a2;
    long long maxi = max(b1, b2);
    long long xxx = maxi - f;
    xxx = xxx / lc;
    xxx = xxx * lc;
    f = f + xxx;
    if (f < maxi) f = f + lc;
    long long ans = findNum(f, r, lc) - findNum(f, l - 1, lc);
    cout << ans << endl;
  }
}

### Prompt

Create a solution in CPP for 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;
long long gcd(long long a, long long b, long long &x, long long &y) {
  if (a == 0) {
    x = 0;
    y = 1;
    return b;
  }
  long long x1, y1;
  long long d = gcd(b % a, a, x1, y1);
  x = y1 - (b / a) * x1;
  y = x1;
  return d;
}
pair<long long, long long> find_any_solution(long long a, long long b,
                                             long long c, long long &x0,
                                             long long &y0, long long &g) {
  g = gcd(abs(a), abs(b), x0, y0);
  if (c % g) {
    return make_pair(-1000000000000000000, -1000000000000000000);
  }
  x0 *= c / g;
  y0 *= c / g;
  if (a < 0) x0 = -x0;
  if (b < 0) y0 = -y0;
  return make_pair(x0, y0);
}
void makeMin(long long &x, long long &y, long long k1, long long k2) {
  long long t = x / k1;
  x = x - (t * k1);
  y = y - (t * k2);
  if (x < 0) {
    x = x + k1;
    y = y + k2;
  }
  if (y < 0) {
    t = y / k2;
    x = x - (t * k1);
    y = y - (t * k2);
    if (y < 0) {
      x = x + k1;
      y = y + k2;
    }
  }
}
long long findNum(long long f, long long x, long long lc) {
  long long ans = x - f;
  if (ans < 0) return 0;
  ans = ans / lc;
  ans++;
  if (ans < 0) ans = 0;
  return ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long a1, b1, a2, b2, l, r;
  cin >> a1 >> b1 >> a2 >> b2 >> l >> r;
  long long a = a1;
  long long b = -a2;
  long long c = b2 - b1;
  long long x, y;
  long long g;
  pair<long long, long long> p = find_any_solution(a, b, c, x, y, g);
  if (p.first == -1000000000000000000)
    cout << 0 << endl;
  else {
    long long k1 = b / g;
    long long k2 = a / g;
    k1 = -k1;
    makeMin(p.first, p.second, k1, k2);
    long long f = a1 * p.first + b1;
    long long lc = a1 / g;
    lc = lc * a2;
    long long maxi = max(b1, b2);
    long long xxx = maxi - f;
    xxx = xxx / lc;
    xxx = xxx * lc;
    f = f + xxx;
    if (f < maxi) f = f + lc;
    long long ans = findNum(f, r, lc) - findNum(f, l - 1, lc);
    cout << ans << endl;
  }
}

```