#include <bits/stdc++.h>
using namespace std;
class GCD {
 private:
  long long int x, y, g = 1;
  void gcd(long long int a, long long int b) {
    if (b == 0) {
      x = 1, y = 0, g = a;
    } else {
      gcd(b, a % b);
      long long int p = y;
      y = x - y * (a / b);
      x = p;
    }
  }

 public:
  void modify(long long int a, long long int b) {
    gcd(a, b);
    if (x < 0) {
      long long int f = ceil(-x * 1.0 / b);
      x = x + (f)*b;
      y = y - (f)*a;
    }
  }
  pair<long long int, long long int> getCoeff() {
    return pair<long long int, long long int>(x, y);
  }
  long long int getGcd() { return g; }
};
long long int a1, a2, b1, b2, L, R;
int main() {
  cin >> a1 >> b1 >> a2 >> b2 >> L >> R;
  if (b1 < b2) {
    swap(b1, b2);
    swap(a1, a2);
  }
  GCD ques;
  ques.modify(a2, a1);
  long long int g = ques.getGcd();
  if (((b1 - b2) % g) != 0) {
    cout << 0;
    return 0;
  } else {
    pair<double, double> c = ques.getCoeff();
    c.first *= ((b1 - b2) / g);
    c.second *= ((b1 - b2) / g);
    c.second *= -1;
    double val = a2 * c.first + b2, lcm = a1 * a2 / ques.getGcd();
    pair<double, double> m = make_pair((L - a2 * c.first - b2) * 1.0 / lcm,
                                       (R - a2 * c.first - b2) * 1.0 / lcm);
    double lb = max(-c.first * 1.0 * a2 / lcm, -c.second * 1.0 * a1 / lcm);
    m.first = max(lb, m.first);
    m.first = ceil(m.first);
    m.second = floor(m.second);
    if (m.second < m.first)
      cout << 0;
    else if (m.second - m.first == 0) {
      if (a1 * c.second + b1 + m.second * lcm < L ||
          a1 * c.second + b1 + m.second * lcm > R) {
        printf("0");
      } else {
        printf("1");
      }
    } else
      printf("%.0f", m.second - m.first + 1);
  }
  return 0;
}

### Prompt

Please formulate 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;
class GCD {
 private:
  long long int x, y, g = 1;
  void gcd(long long int a, long long int b) {
    if (b == 0) {
      x = 1, y = 0, g = a;
    } else {
      gcd(b, a % b);
      long long int p = y;
      y = x - y * (a / b);
      x = p;
    }
  }

 public:
  void modify(long long int a, long long int b) {
    gcd(a, b);
    if (x < 0) {
      long long int f = ceil(-x * 1.0 / b);
      x = x + (f)*b;
      y = y - (f)*a;
    }
  }
  pair<long long int, long long int> getCoeff() {
    return pair<long long int, long long int>(x, y);
  }
  long long int getGcd() { return g; }
};
long long int a1, a2, b1, b2, L, R;
int main() {
  cin >> a1 >> b1 >> a2 >> b2 >> L >> R;
  if (b1 < b2) {
    swap(b1, b2);
    swap(a1, a2);
  }
  GCD ques;
  ques.modify(a2, a1);
  long long int g = ques.getGcd();
  if (((b1 - b2) % g) != 0) {
    cout << 0;
    return 0;
  } else {
    pair<double, double> c = ques.getCoeff();
    c.first *= ((b1 - b2) / g);
    c.second *= ((b1 - b2) / g);
    c.second *= -1;
    double val = a2 * c.first + b2, lcm = a1 * a2 / ques.getGcd();
    pair<double, double> m = make_pair((L - a2 * c.first - b2) * 1.0 / lcm,
                                       (R - a2 * c.first - b2) * 1.0 / lcm);
    double lb = max(-c.first * 1.0 * a2 / lcm, -c.second * 1.0 * a1 / lcm);
    m.first = max(lb, m.first);
    m.first = ceil(m.first);
    m.second = floor(m.second);
    if (m.second < m.first)
      cout << 0;
    else if (m.second - m.first == 0) {
      if (a1 * c.second + b1 + m.second * lcm < L ||
          a1 * c.second + b1 + m.second * lcm > R) {
        printf("0");
      } else {
        printf("1");
      }
    } else
      printf("%.0f", m.second - m.first + 1);
  }
  return 0;
}

```