#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
const int INF = 0x3f3f3f3f;
const long long INFF = 0x3f3f;
const double pi = acos(-1.0);
const double inf = 1e18;
const double eps = 1e-4;
const long long mod = 1e9 + 7;
const unsigned long long mx = 133333331;
inline void RI(int &x) {
  char c;
  while ((c = getchar()) < '0' || c > '9')
    ;
  x = c - '0';
  while ((c = getchar()) >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0';
}
void exgcd(long long a, long long b, long long &d, long long &x, long long &y) {
  if (!b) {
    x = 1;
    y = 0;
    d = a;
    return;
  } else {
    exgcd(b, a % b, d, y, x);
    y -= a / b * x;
  }
}
long long labs(long long a) {
  if (a < 0) return -a;
  return a;
}
int main() {
  long long a1, b1, a2, b2, L, R;
  while (cin >> a1 >> b1 >> a2 >> b2 >> L >> R) {
    long long x, y, d;
    exgcd(a1, a2, d, x, y);
    if ((b2 - b1) % d != 0) {
      cout << 0 << endl;
      continue;
    }
    x *= (b2 - b1) / d;
    x = (x % labs(a2 / d) + labs(a2 / d)) % labs(a2 / d);
    long long cnt = x * a1 + b1;
    long long tmp = labs(a1 * a2 / d);
    long long ans = 0;
    L = max(L, max(b1, b2));
    if (L > R) {
      cout << 0 << endl;
      continue;
    }
    if (cnt <= R) ans += (R - cnt) / tmp + 1;
    if (cnt < L) ans -= (L - 1 - cnt) / tmp + 1;
    cout << ans << endl;
  }
  return 0;
}

### Prompt

Please create a solution in cpp 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>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
const int INF = 0x3f3f3f3f;
const long long INFF = 0x3f3f;
const double pi = acos(-1.0);
const double inf = 1e18;
const double eps = 1e-4;
const long long mod = 1e9 + 7;
const unsigned long long mx = 133333331;
inline void RI(int &x) {
  char c;
  while ((c = getchar()) < '0' || c > '9')
    ;
  x = c - '0';
  while ((c = getchar()) >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0';
}
void exgcd(long long a, long long b, long long &d, long long &x, long long &y) {
  if (!b) {
    x = 1;
    y = 0;
    d = a;
    return;
  } else {
    exgcd(b, a % b, d, y, x);
    y -= a / b * x;
  }
}
long long labs(long long a) {
  if (a < 0) return -a;
  return a;
}
int main() {
  long long a1, b1, a2, b2, L, R;
  while (cin >> a1 >> b1 >> a2 >> b2 >> L >> R) {
    long long x, y, d;
    exgcd(a1, a2, d, x, y);
    if ((b2 - b1) % d != 0) {
      cout << 0 << endl;
      continue;
    }
    x *= (b2 - b1) / d;
    x = (x % labs(a2 / d) + labs(a2 / d)) % labs(a2 / d);
    long long cnt = x * a1 + b1;
    long long tmp = labs(a1 * a2 / d);
    long long ans = 0;
    L = max(L, max(b1, b2));
    if (L > R) {
      cout << 0 << endl;
      continue;
    }
    if (cnt <= R) ans += (R - cnt) / tmp + 1;
    if (cnt < L) ans -= (L - 1 - cnt) / tmp + 1;
    cout << ans << endl;
  }
  return 0;
}

```