#include <bits/stdc++.h>
using namespace std;
void exgcd(long long a, long long& x, long long b, long long& y, long long& g) {
  if (b == 0) {
    y = 0;
    g = abs(a);
    x = g / a;
  } else {
    exgcd(b, y, a % b, x, g);
    y -= a / b * x;
  }
}
long long fl(long long a, long long b) {
  if (b < 0) b = -b, a = -a;
  if (a >= 0) return a / b;
  return ((-a + b - 1) / b) * (-1);
}
long long cl(long long a, long long b) {
  if (b < 0) b = -b, a = -a;
  if (a >= 0) return (a + b - 1) / b;
  return a / b;
}
long long a1, b1, a2, b2, L, R;
int main() {
  cin >> a1 >> b1 >> a2 >> b2 >> L >> R;
  long long x0, y0, g;
  exgcd(a1, x0, -a2, y0, g);
  long long c = b2 - b1;
  if (c % g) {
    cout << "0\n";
    return 0;
  }
  x0 *= c / g, y0 *= c / g;
  long long dx = a2 / g, dy = a1 / g;
  long long dt = min(fl(x0, dx), fl(y0, dy));
  x0 -= dt * dx, y0 -= dt * dy;
  long long l = max(0ll, cl(L - b1 - a1 * x0, a1 * dx)),
            r = fl(R - b1 - a1 * x0, a1 * dx);
  if (r < l)
    cout << "0\n";
  else
    cout << r - l + 1 << endl;
}

### 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;
void exgcd(long long a, long long& x, long long b, long long& y, long long& g) {
  if (b == 0) {
    y = 0;
    g = abs(a);
    x = g / a;
  } else {
    exgcd(b, y, a % b, x, g);
    y -= a / b * x;
  }
}
long long fl(long long a, long long b) {
  if (b < 0) b = -b, a = -a;
  if (a >= 0) return a / b;
  return ((-a + b - 1) / b) * (-1);
}
long long cl(long long a, long long b) {
  if (b < 0) b = -b, a = -a;
  if (a >= 0) return (a + b - 1) / b;
  return a / b;
}
long long a1, b1, a2, b2, L, R;
int main() {
  cin >> a1 >> b1 >> a2 >> b2 >> L >> R;
  long long x0, y0, g;
  exgcd(a1, x0, -a2, y0, g);
  long long c = b2 - b1;
  if (c % g) {
    cout << "0\n";
    return 0;
  }
  x0 *= c / g, y0 *= c / g;
  long long dx = a2 / g, dy = a1 / g;
  long long dt = min(fl(x0, dx), fl(y0, dy));
  x0 -= dt * dx, y0 -= dt * dy;
  long long l = max(0ll, cl(L - b1 - a1 * x0, a1 * dx)),
            r = fl(R - b1 - a1 * x0, a1 * dx);
  if (r < l)
    cout << "0\n";
  else
    cout << r - l + 1 << endl;
}

```