#include <bits/stdc++.h>
using namespace std;
long long a1, a2, b1, b2, L, R, x, k, l, ans;
long long ex_gcd(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1, y = 0;
    return a;
  }
  long long res = ex_gcd(b, a % b, y, x);
  y -= (a / b * x);
  return res;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> a1 >> b1 >> a2 >> b2 >> L >> R;
  if (a1 < a2) {
    swap(a1, a2);
    swap(b1, b2);
  }
  long long d = ex_gcd(a1, a2, k, l), C = b1 - b2, p = C / d;
  if (C % d) {
    cout << "0\n";
    return 0;
  }
  k = -k;
  k = ((k % a2) * (p % a2)) % a2;
  l = ((l % a1) * (p % a1)) % a1;
  x = a2 * l + b2;
  L = max(max(b1, b2), L);
  if (L > R) {
    cout << "0\n";
    return 0;
  }
  d = (a1 * a2 / d);
  if (x >= L) x -= (d * ((x - L) / d + 1));
  long long i = (L - x - 1) / d, j = (R - x) / d;
  ans = max(0ll, j - i);
  cout << ans << "\n";
  return 0;
}

### Prompt

Please create a solution in CPP 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;
long long a1, a2, b1, b2, L, R, x, k, l, ans;
long long ex_gcd(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1, y = 0;
    return a;
  }
  long long res = ex_gcd(b, a % b, y, x);
  y -= (a / b * x);
  return res;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> a1 >> b1 >> a2 >> b2 >> L >> R;
  if (a1 < a2) {
    swap(a1, a2);
    swap(b1, b2);
  }
  long long d = ex_gcd(a1, a2, k, l), C = b1 - b2, p = C / d;
  if (C % d) {
    cout << "0\n";
    return 0;
  }
  k = -k;
  k = ((k % a2) * (p % a2)) % a2;
  l = ((l % a1) * (p % a1)) % a1;
  x = a2 * l + b2;
  L = max(max(b1, b2), L);
  if (L > R) {
    cout << "0\n";
    return 0;
  }
  d = (a1 * a2 / d);
  if (x >= L) x -= (d * ((x - L) / d + 1));
  long long i = (L - x - 1) / d, j = (R - x) / d;
  ans = max(0ll, j - i);
  cout << ans << "\n";
  return 0;
}

```