#include <bits/stdc++.h>
using namespace std;
template <class X, class Y>
void minimize(X &x, const Y &y) {
  if (x > y) x = y;
}
template <class X, class Y>
void maximize(X &x, const Y &y) {
  if (x < y) x = y;
}
template <class T>
T Abs(const T &x) {
  return (x < 0 ? -x : x);
}
long long floor(long long a, long long b) {
  assert(b > 0);
  long long x = a / b;
  for (int i = (2), _a = (-2); i >= _a; i = i - 1)
    if (b * (x + i) <= a) return (x + i);
  assert(false);
}
long long ceil(long long a, long long b) {
  assert(b > 0);
  long long x = a / b;
  for (int i = (-2), _b = (2); i <= _b; i = i + 1)
    if (b * (x + i) >= a) return (x + i);
  assert(false);
}
long long gcd(long long a, long long b) {
  while (true) {
    if (a == 0) return (b);
    if (b == 0) return (a);
    if (a > b)
      a %= b;
    else
      b %= a;
  }
}
long long calcNumber(long long a1, long long a2, long long b1, long long b2,
                     long long L, long long R) {
  maximize(L, b1);
  maximize(L, b2);
  long long d = gcd(a1, a2);
  if ((b2 - b1) % d != 0) return (0);
  long long c1 = a1 / d;
  long long c2 = a2 / d;
  long long c = (b2 - b1) / d;
  long long r[2], s[2], t[2];
  r[0] = c1;
  s[0] = 1;
  t[0] = 0;
  r[1] = c2;
  s[1] = 0;
  t[1] = 1;
  int cur = 1;
  while (r[cur] != 0) {
    int ___next = cur ^ 1;
    long long q = r[___next] / r[cur];
    r[___next] -= q * r[cur];
    s[___next] -= q * s[cur];
    t[___next] -= q * t[cur];
    cur = ___next;
  }
  assert(r[cur ^ 1] == 1);
  long long valX = s[cur ^ 1] % c2 * c % c2;
  if (valX < 0) valX += c2;
  assert((valX * c1 - c) % c2 == 0);
  long long minX = ceil(L - b1, a1);
  long long maxX = floor(R - b1, a1);
  if (minX > maxX) return (0);
  long long minK = ceil(minX - valX, c2);
  long long maxK = floor(maxX - valX, c2);
  if (minK > maxK) return (0);
  return (maxK - minK + 1);
}
int main(void) {
  long long a1, b1, a2, b2, L, R;
  cin >> a1 >> b1 >> a2 >> b2 >> L >> R;
  cout << calcNumber(a1, a2, b1, b2, L, R) << 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;
template <class X, class Y>
void minimize(X &x, const Y &y) {
  if (x > y) x = y;
}
template <class X, class Y>
void maximize(X &x, const Y &y) {
  if (x < y) x = y;
}
template <class T>
T Abs(const T &x) {
  return (x < 0 ? -x : x);
}
long long floor(long long a, long long b) {
  assert(b > 0);
  long long x = a / b;
  for (int i = (2), _a = (-2); i >= _a; i = i - 1)
    if (b * (x + i) <= a) return (x + i);
  assert(false);
}
long long ceil(long long a, long long b) {
  assert(b > 0);
  long long x = a / b;
  for (int i = (-2), _b = (2); i <= _b; i = i + 1)
    if (b * (x + i) >= a) return (x + i);
  assert(false);
}
long long gcd(long long a, long long b) {
  while (true) {
    if (a == 0) return (b);
    if (b == 0) return (a);
    if (a > b)
      a %= b;
    else
      b %= a;
  }
}
long long calcNumber(long long a1, long long a2, long long b1, long long b2,
                     long long L, long long R) {
  maximize(L, b1);
  maximize(L, b2);
  long long d = gcd(a1, a2);
  if ((b2 - b1) % d != 0) return (0);
  long long c1 = a1 / d;
  long long c2 = a2 / d;
  long long c = (b2 - b1) / d;
  long long r[2], s[2], t[2];
  r[0] = c1;
  s[0] = 1;
  t[0] = 0;
  r[1] = c2;
  s[1] = 0;
  t[1] = 1;
  int cur = 1;
  while (r[cur] != 0) {
    int ___next = cur ^ 1;
    long long q = r[___next] / r[cur];
    r[___next] -= q * r[cur];
    s[___next] -= q * s[cur];
    t[___next] -= q * t[cur];
    cur = ___next;
  }
  assert(r[cur ^ 1] == 1);
  long long valX = s[cur ^ 1] % c2 * c % c2;
  if (valX < 0) valX += c2;
  assert((valX * c1 - c) % c2 == 0);
  long long minX = ceil(L - b1, a1);
  long long maxX = floor(R - b1, a1);
  if (minX > maxX) return (0);
  long long minK = ceil(minX - valX, c2);
  long long maxK = floor(maxX - valX, c2);
  if (minK > maxK) return (0);
  return (maxK - minK + 1);
}
int main(void) {
  long long a1, b1, a2, b2, L, R;
  cin >> a1 >> b1 >> a2 >> b2 >> L >> R;
  cout << calcNumber(a1, a2, b1, b2, L, R) << endl;
  return 0;
}

```