#include <bits/stdc++.h>
using namespace std;
long long exGcd(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long r = exGcd(b, a % b, x, y);
  long long t = x;
  x = y;
  y = t - a / b * y;
  return r;
}
int main() {
  long long a1, b1, a2, b2, L, R;
  cin >> a1 >> b1 >> a2 >> b2 >> L >> R;
  b2 -= b1, L -= b1, R -= b1, b1 -= b1;
  long long k, l;
  long long gcd = exGcd(a1, a2, k, l);
  if (b2 % gcd) {
    cout << 0 << endl;
    return 0;
  }
  a1 /= gcd, a2 /= gcd, b2 /= gcd;
  if (L < 0)
    L = 0;
  else
    L = (L + gcd - 1) / gcd;
  if (R < 0)
    R = -1;
  else
    R /= gcd;
  gcd = exGcd(a1, -a2, k, l);
  if (k * a1 - l * a2 < 0) k = -k, l = -l;
  k *= b2, l *= b2;
  long long d = a1 * a2, x = a1 * (k % d);
  double tp = 1.0 * a1 * (k % d);
  x = tp - 1.0 * ((long long)(tp / d)) * d;
  x -= ((int)2e10 / d) * d;
  L = max(L, 0ll);
  L = max(L, b2);
  R = max(-1ll, R);
  cout << max(0ll, (R - x + d) / d - (L - 1 - x + d) / d) << endl;
  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>
using namespace std;
long long exGcd(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long r = exGcd(b, a % b, x, y);
  long long t = x;
  x = y;
  y = t - a / b * y;
  return r;
}
int main() {
  long long a1, b1, a2, b2, L, R;
  cin >> a1 >> b1 >> a2 >> b2 >> L >> R;
  b2 -= b1, L -= b1, R -= b1, b1 -= b1;
  long long k, l;
  long long gcd = exGcd(a1, a2, k, l);
  if (b2 % gcd) {
    cout << 0 << endl;
    return 0;
  }
  a1 /= gcd, a2 /= gcd, b2 /= gcd;
  if (L < 0)
    L = 0;
  else
    L = (L + gcd - 1) / gcd;
  if (R < 0)
    R = -1;
  else
    R /= gcd;
  gcd = exGcd(a1, -a2, k, l);
  if (k * a1 - l * a2 < 0) k = -k, l = -l;
  k *= b2, l *= b2;
  long long d = a1 * a2, x = a1 * (k % d);
  double tp = 1.0 * a1 * (k % d);
  x = tp - 1.0 * ((long long)(tp / d)) * d;
  x -= ((int)2e10 / d) * d;
  L = max(L, 0ll);
  L = max(L, b2);
  R = max(-1ll, R);
  cout << max(0ll, (R - x + d) / d - (L - 1 - x + d) / d) << endl;
  return 0;
}

```