#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';
}
vector<int> a, b;
long long mul(long long a, long long b, long long mod) {
  long long n = 0;
  while (b) {
    if (b & 1) n = (n + a) % mod;
    a = (a * 2) % mod;
    b /= 2;
  }
  return n;
}
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;
}
long long solve() {
  long long ta = a[0], tb = b[0];
  int flag = 1;
  for (int i = 1; i < a.size(); i++) {
    long long xa = ta, xb = a[i], c = b[i] - tb, d, x, y;
    exgcd(xa, xb, d, x, y);
    if (c % d) {
      flag = 0;
      break;
    }
    long long tmp = xb / d;
    long long k = 1;
    if (x < 0) k *= -1;
    if (c / d < 0) k *= -1;
    x = (mul(labs(x), labs(c / d), tmp) * k + tmp) % tmp;
    tb = ta * x + tb;
    ta = ta / d * a[i];
  }
  if (!flag) return -INF;
  return tb;
}
long long gcd(long long x, long long y) {
  if (!y) return x;
  return gcd(y, x % y);
}
long long lcm(long long x, long long y) { return x * y / gcd(x, y); }
int main() {
  long long a1, b1, a2, b2, L, R;
  while (cin >> a1 >> b1 >> a2 >> b2 >> L >> R) {
    a.clear();
    b.clear();
    a.push_back(a1);
    a.push_back(a2);
    b.push_back(b1);
    b.push_back(b2);
    long long cnt = solve();
    L = max(max(b1, b2), L);
    if (L > R) {
      cout << 0 << endl;
      continue;
    }
    if (cnt == -INF) {
      cout << 0 << endl;
      continue;
    }
    long long tmp = lcm(a1, a2);
    long long ans = 0;
    if (cnt <= R) ans += (R - cnt) / tmp + 1;
    if (cnt < L) ans -= (L - 1 - cnt) / tmp + 1;
    cout << ans << endl;
  }
  return 0;
}

### Prompt

In Cpp, your task is to solve 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';
}
vector<int> a, b;
long long mul(long long a, long long b, long long mod) {
  long long n = 0;
  while (b) {
    if (b & 1) n = (n + a) % mod;
    a = (a * 2) % mod;
    b /= 2;
  }
  return n;
}
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;
}
long long solve() {
  long long ta = a[0], tb = b[0];
  int flag = 1;
  for (int i = 1; i < a.size(); i++) {
    long long xa = ta, xb = a[i], c = b[i] - tb, d, x, y;
    exgcd(xa, xb, d, x, y);
    if (c % d) {
      flag = 0;
      break;
    }
    long long tmp = xb / d;
    long long k = 1;
    if (x < 0) k *= -1;
    if (c / d < 0) k *= -1;
    x = (mul(labs(x), labs(c / d), tmp) * k + tmp) % tmp;
    tb = ta * x + tb;
    ta = ta / d * a[i];
  }
  if (!flag) return -INF;
  return tb;
}
long long gcd(long long x, long long y) {
  if (!y) return x;
  return gcd(y, x % y);
}
long long lcm(long long x, long long y) { return x * y / gcd(x, y); }
int main() {
  long long a1, b1, a2, b2, L, R;
  while (cin >> a1 >> b1 >> a2 >> b2 >> L >> R) {
    a.clear();
    b.clear();
    a.push_back(a1);
    a.push_back(a2);
    b.push_back(b1);
    b.push_back(b2);
    long long cnt = solve();
    L = max(max(b1, b2), L);
    if (L > R) {
      cout << 0 << endl;
      continue;
    }
    if (cnt == -INF) {
      cout << 0 << endl;
      continue;
    }
    long long tmp = lcm(a1, a2);
    long long ans = 0;
    if (cnt <= R) ans += (R - cnt) / tmp + 1;
    if (cnt < L) ans -= (L - 1 - cnt) / tmp + 1;
    cout << ans << endl;
  }
  return 0;
}

```