#include <bits/stdc++.h>
using namespace std;
long long x, y, d;
void bezo(long long a, long long b) {
  if (b == 0) {
    x = 1;
    y = 0;
    d = a;
    return;
  }
  bezo(b, a % b);
  long long x1 = y;
  long long y1 = x - (a / b) * y;
  x = x1;
  y = y1;
}
int main() {
  long long a1, b1, a2, b2, l, r, lcm, ans = 0, n;
  cin >> a1 >> b1 >> a2 >> b2 >> l >> r;
  bezo(a1, -a2);
  lcm = a1 * a2 / abs(d);
  if ((b2 - b1) % d == 0) {
    x = (x * (b2 - b1)) / d;
    y = (y * (b2 - b1)) / d;
    if (d < 0) d = -d;
    if (x > 0 && y > 0) {
      long long n1, n2;
      n1 = x / (a2 / d);
      n2 = y / (a1 / d);
      x -= min(n1, n2) * (a2 / d);
      y -= min(n1, n2) * (a1 / d);
    }
    if (x < 0) {
      long long t = a2 / d;
      n = x / t;
      n = -n;
      x += n * t;
      if (x < 0) {
        x += t;
        n++;
      }
      y += n * (a1 / d);
    }
    if (y < 0) {
      long long t = a1 / d;
      n = y / t;
      n = -n;
      y += n * t;
      if (y < 0) {
        y += t;
        n++;
      }
      x += n * (a2 / d);
    }
    long long p = x * a1 + b1;
    if (p < l) {
      p += ((l - p) / lcm) * lcm;
      if (p < l) p += lcm;
    }
    if (p <= r) {
      ans = 1;
      ans += (r - p) / lcm;
    } else
      ans = 0;
  } else
    ans = 0;
  cout << ans;
  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;
long long x, y, d;
void bezo(long long a, long long b) {
  if (b == 0) {
    x = 1;
    y = 0;
    d = a;
    return;
  }
  bezo(b, a % b);
  long long x1 = y;
  long long y1 = x - (a / b) * y;
  x = x1;
  y = y1;
}
int main() {
  long long a1, b1, a2, b2, l, r, lcm, ans = 0, n;
  cin >> a1 >> b1 >> a2 >> b2 >> l >> r;
  bezo(a1, -a2);
  lcm = a1 * a2 / abs(d);
  if ((b2 - b1) % d == 0) {
    x = (x * (b2 - b1)) / d;
    y = (y * (b2 - b1)) / d;
    if (d < 0) d = -d;
    if (x > 0 && y > 0) {
      long long n1, n2;
      n1 = x / (a2 / d);
      n2 = y / (a1 / d);
      x -= min(n1, n2) * (a2 / d);
      y -= min(n1, n2) * (a1 / d);
    }
    if (x < 0) {
      long long t = a2 / d;
      n = x / t;
      n = -n;
      x += n * t;
      if (x < 0) {
        x += t;
        n++;
      }
      y += n * (a1 / d);
    }
    if (y < 0) {
      long long t = a1 / d;
      n = y / t;
      n = -n;
      y += n * t;
      if (y < 0) {
        y += t;
        n++;
      }
      x += n * (a2 / d);
    }
    long long p = x * a1 + b1;
    if (p < l) {
      p += ((l - p) / lcm) * lcm;
      if (p < l) p += lcm;
    }
    if (p <= r) {
      ans = 1;
      ans += (r - p) / lcm;
    } else
      ans = 0;
  } else
    ans = 0;
  cout << ans;
  return 0;
}

```