#include <bits/stdc++.h>
using namespace std;
long long int gcd(long long int a, long long int b) {
  if (a % b == 0) {
    return b;
  }
  return gcd(b, a % b);
}
void ex_gcd(long long int a, long long int b, long long int &x,
            long long int &y) {
  if (!b) {
    x = 1;
    y = 0;
  } else {
    ex_gcd(b, a % b, y, x);
    y -= x * (a / b);
  }
}
int main() {
  long long int a1, a2, b1, b2, L, R, a, b, c, g, x, y, _b, lcm, begin;
  long long int l, r;
  cin >> a1 >> b1 >> a2 >> b2 >> L >> R;
  a = a1;
  b = -a2;
  c = b2 - b1;
  g = gcd(a, b);
  if (c % g != 0) {
    cout << 0;
    return 0;
  }
  ex_gcd(a, b, x, y);
  x = x * c / g;
  y = y * c / g;
  _b = abs(b / g);
  if ((L - b1) % a1 == 0)
    l = (L - b1) / a1;
  else
    l = (L - b1) < 0 ? (L - b1) / a1 : (L - b1) / a1 + 1;
  if ((R - b1) % a1 == 0)
    r = (R - b1) / a1;
  else
    r = (R - b1) < 0 ? (R - b1) / a1 - 1 : (R - b1) / a1;
  if (r < 0) {
    cout << 0;
    return 0;
  } else if (l < 0) {
    l = 0;
  }
  if ((l - x) % _b == 0)
    L = (l - x) / _b;
  else
    L = (l - x) < 0 ? (l - x) / _b : (l - x) / _b + 1;
  if ((r - x) % _b == 0)
    R = (r - x) / _b;
  else
    R = (r - x) < 0 ? (r - x) / _b - 1 : (r - x) / _b;
  if (R < L)
    cout << 0;
  else {
    long long int cnt = R - L + 1;
    lcm = a1 * a2 / gcd(a1, a2);
    if (a1 * (x + L * _b) + b1 >= b2) {
      cout << cnt;
    } else {
      long long int temp = b2 - (a1 * (x + L * _b) + b1);
      if (temp % lcm != 0)
        cnt = cnt - temp / lcm - 1;
      else
        cnt = cnt - temp / lcm;
      if (cnt <= 0)
        cout << 0;
      else
        cout << cnt;
    }
  }
  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;
long long int gcd(long long int a, long long int b) {
  if (a % b == 0) {
    return b;
  }
  return gcd(b, a % b);
}
void ex_gcd(long long int a, long long int b, long long int &x,
            long long int &y) {
  if (!b) {
    x = 1;
    y = 0;
  } else {
    ex_gcd(b, a % b, y, x);
    y -= x * (a / b);
  }
}
int main() {
  long long int a1, a2, b1, b2, L, R, a, b, c, g, x, y, _b, lcm, begin;
  long long int l, r;
  cin >> a1 >> b1 >> a2 >> b2 >> L >> R;
  a = a1;
  b = -a2;
  c = b2 - b1;
  g = gcd(a, b);
  if (c % g != 0) {
    cout << 0;
    return 0;
  }
  ex_gcd(a, b, x, y);
  x = x * c / g;
  y = y * c / g;
  _b = abs(b / g);
  if ((L - b1) % a1 == 0)
    l = (L - b1) / a1;
  else
    l = (L - b1) < 0 ? (L - b1) / a1 : (L - b1) / a1 + 1;
  if ((R - b1) % a1 == 0)
    r = (R - b1) / a1;
  else
    r = (R - b1) < 0 ? (R - b1) / a1 - 1 : (R - b1) / a1;
  if (r < 0) {
    cout << 0;
    return 0;
  } else if (l < 0) {
    l = 0;
  }
  if ((l - x) % _b == 0)
    L = (l - x) / _b;
  else
    L = (l - x) < 0 ? (l - x) / _b : (l - x) / _b + 1;
  if ((r - x) % _b == 0)
    R = (r - x) / _b;
  else
    R = (r - x) < 0 ? (r - x) / _b - 1 : (r - x) / _b;
  if (R < L)
    cout << 0;
  else {
    long long int cnt = R - L + 1;
    lcm = a1 * a2 / gcd(a1, a2);
    if (a1 * (x + L * _b) + b1 >= b2) {
      cout << cnt;
    } else {
      long long int temp = b2 - (a1 * (x + L * _b) + b1);
      if (temp % lcm != 0)
        cnt = cnt - temp / lcm - 1;
      else
        cnt = cnt - temp / lcm;
      if (cnt <= 0)
        cout << 0;
      else
        cout << cnt;
    }
  }
  return 0;
}

```