#include <bits/stdc++.h>
using namespace std;
const long long t = 3e9;
int a[10], m[10];
long long extgcd(long long a, long long b, long long &x, long long &y) {
  if (a == 0 && b == 0) return -1;
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long d = extgcd(b, a % b, y, x);
  y -= a / b * x;
  return d;
}
bool solve(long long &m0, long long &a0, long long m, long long a) {
  long long y, x;
  long long g = extgcd(m0, m, x, y);
  if (abs(a - a0) % g) return false;
  x *= (a - a0) / g;
  x %= m / g;
  a0 = x * m0 + a0;
  m0 *= m / g;
  a0 %= m0;
  if (a0 < 0) a0 += m0;
  return true;
}
bool mles(long long &m0, long long &a0, int n) {
  m0 = 1;
  a0 = 0;
  for (int i = 0; i < n; ++i)
    if (!solve(m0, a0, m[i], a[i])) return false;
  return true;
}
int main() {
  for (int i = 0; i < 2; ++i) cin >> m[i] >> a[i];
  long long l, r;
  cin >> l >> r;
  l = max(l, (long long)max(a[0], a[1]));
  for (int i = 0; i < 2; ++i) {
    a[i] %= m[i];
    if (a[i] < 0) a[i] += m[i];
  }
  long long ans = 0, m0, a0;
  if (l <= r && mles(m0, a0, 2)) {
    long long tmp = t / m0 + 1;
    l += tmp * m0, r += tmp * m0;
    if (a0 < l)
      ans = (r - a0) / m0 - (l - a0 + m0 - 1) / m0 + 1;
    else if (a0 <= r)
      ans = (r - a0) / m0 + 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>
using namespace std;
const long long t = 3e9;
int a[10], m[10];
long long extgcd(long long a, long long b, long long &x, long long &y) {
  if (a == 0 && b == 0) return -1;
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long d = extgcd(b, a % b, y, x);
  y -= a / b * x;
  return d;
}
bool solve(long long &m0, long long &a0, long long m, long long a) {
  long long y, x;
  long long g = extgcd(m0, m, x, y);
  if (abs(a - a0) % g) return false;
  x *= (a - a0) / g;
  x %= m / g;
  a0 = x * m0 + a0;
  m0 *= m / g;
  a0 %= m0;
  if (a0 < 0) a0 += m0;
  return true;
}
bool mles(long long &m0, long long &a0, int n) {
  m0 = 1;
  a0 = 0;
  for (int i = 0; i < n; ++i)
    if (!solve(m0, a0, m[i], a[i])) return false;
  return true;
}
int main() {
  for (int i = 0; i < 2; ++i) cin >> m[i] >> a[i];
  long long l, r;
  cin >> l >> r;
  l = max(l, (long long)max(a[0], a[1]));
  for (int i = 0; i < 2; ++i) {
    a[i] %= m[i];
    if (a[i] < 0) a[i] += m[i];
  }
  long long ans = 0, m0, a0;
  if (l <= r && mles(m0, a0, 2)) {
    long long tmp = t / m0 + 1;
    l += tmp * m0, r += tmp * m0;
    if (a0 < l)
      ans = (r - a0) / m0 - (l - a0 + m0 - 1) / m0 + 1;
    else if (a0 <= r)
      ans = (r - a0) / m0 + 1;
  }
  cout << ans << endl;
  return 0;
}

```