#include <bits/stdc++.h>
using namespace std;
void base() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
}
__int128 extended_euclid(__int128 a, __int128 b, __int128 &x, __int128 &y) {
  __int128 xx = y = 0;
  __int128 yy = x = 1;
  while (b) {
    __int128 q = a / b;
    __int128 t = b;
    b = a % b;
    a = t;
    t = xx;
    xx = x - q * xx;
    x = t;
    t = yy;
    yy = y - q * yy;
    y = t;
  }
  return a;
}
void solve() {
  long long a1, a2, b1, b2, l, r;
  cin >> a1 >> b1 >> a2 >> b2 >> l >> r;
  __int128 x, y;
  __int128 g = extended_euclid(a1, -a2, x, y);
  __int128 c = b2 - b1;
  if ((c % g) != 0) {
    cout << "0\n";
    return;
  }
  if (g < 0) {
    g = -g;
    x = -x;
    y = -y;
  }
  __int128 lcm = a1 / g * a2;
  __int128 xx = ((c / g * x) % lcm + lcm) % lcm;
  xx = ((xx * a1) % lcm + lcm) % lcm;
  xx = ((xx + b1) % lcm + lcm) % lcm;
  l = max(l, max(b1, b2));
  __int128 ri = (8e18 - xx) / lcm;
  __int128 le = (-8e18 - xx) / lcm;
  long long ansr = le;
  long long ansl = ri;
  while (le <= ri) {
    __int128 m = (le + ri) >> 1;
    if (m * lcm + xx <= r) {
      le = m + 1;
      ansr = m;
    } else {
      ri = m - 1;
    }
  }
  ri = (8e18 - xx) / lcm;
  le = (-8e18 - xx) / lcm;
  while (le <= ri) {
    __int128 m = (le + ri) >> 1;
    if (m * lcm + xx >= l) {
      ri = m - 1;
      ansl = m;
    } else {
      le = m + 1;
    }
  }
  cout << max(ansr - ansl + 1, 0ll) << "\n";
}
int main() {
  base();
  int t = 1;
  while (t--) {
    solve();
  }
  return 0;
}

### Prompt

Your task is to create 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;
void base() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
}
__int128 extended_euclid(__int128 a, __int128 b, __int128 &x, __int128 &y) {
  __int128 xx = y = 0;
  __int128 yy = x = 1;
  while (b) {
    __int128 q = a / b;
    __int128 t = b;
    b = a % b;
    a = t;
    t = xx;
    xx = x - q * xx;
    x = t;
    t = yy;
    yy = y - q * yy;
    y = t;
  }
  return a;
}
void solve() {
  long long a1, a2, b1, b2, l, r;
  cin >> a1 >> b1 >> a2 >> b2 >> l >> r;
  __int128 x, y;
  __int128 g = extended_euclid(a1, -a2, x, y);
  __int128 c = b2 - b1;
  if ((c % g) != 0) {
    cout << "0\n";
    return;
  }
  if (g < 0) {
    g = -g;
    x = -x;
    y = -y;
  }
  __int128 lcm = a1 / g * a2;
  __int128 xx = ((c / g * x) % lcm + lcm) % lcm;
  xx = ((xx * a1) % lcm + lcm) % lcm;
  xx = ((xx + b1) % lcm + lcm) % lcm;
  l = max(l, max(b1, b2));
  __int128 ri = (8e18 - xx) / lcm;
  __int128 le = (-8e18 - xx) / lcm;
  long long ansr = le;
  long long ansl = ri;
  while (le <= ri) {
    __int128 m = (le + ri) >> 1;
    if (m * lcm + xx <= r) {
      le = m + 1;
      ansr = m;
    } else {
      ri = m - 1;
    }
  }
  ri = (8e18 - xx) / lcm;
  le = (-8e18 - xx) / lcm;
  while (le <= ri) {
    __int128 m = (le + ri) >> 1;
    if (m * lcm + xx >= l) {
      ri = m - 1;
      ansl = m;
    } else {
      le = m + 1;
    }
  }
  cout << max(ansr - ansl + 1, 0ll) << "\n";
}
int main() {
  base();
  int t = 1;
  while (t--) {
    solve();
  }
  return 0;
}

```