#include <bits/stdc++.h>
const long long MAX_N = (long long)1e5 + 123;
using namespace std;
pair<long long, long long> calc(long long L, long long R, long long a) {
  if (R >= 0)
    R /= a;
  else {
    if (R % a == 0)
      R /= a;
    else
      R = R / a - 1;
  }
  if (L >= 0) {
    if (L % a == 0)
      L /= a;
    else
      L = L / a + 1;
  } else
    L /= a;
  return make_pair(L, R);
}
struct num {
  long long a, b;
  long long l, r;
  void in() { cin >> a >> b; }
  void calc_seg(long long L, long long R) {
    pair<long long, long long> now = calc(L - b, R - b, a);
    l = max(now.first, 0ll), r = now.second;
    if (l > r) {
      cout << "0";
      exit(0);
    }
  }
} first, second;
long long l, r;
long long gcd(long long a, long long b, long long& x, long long& y) {
  if (a == 0) {
    x = 0;
    y = 1;
    return b;
  }
  long long x1, y1;
  long long d = gcd(b % a, a, x1, y1);
  x = y1 - (b / a) * x1;
  y = x1;
  return d;
}
bool find_any_solution(long long a, long long b, long long c, long long& x0,
                       long long& y0, long long& g) {
  g = gcd(abs(a), abs(b), x0, y0);
  if (c % g != 0) return false;
  x0 *= c / g;
  y0 *= c / g;
  if (a < 0) x0 *= -1;
  if (b < 0) y0 *= -1;
  return true;
}
long long calc(num first, num second) {
  long long A = first.a, B = -second.a, C = second.b - first.b;
  long long x0, y0, g;
  if (!find_any_solution(A, B, C, x0, y0, g)) {
    cout << "0";
    exit(0);
  }
  B /= g;
  first.l -= x0, first.r -= x0;
  first.l *= -1, first.r *= -1, B *= -1;
  swap(first.l, first.r);
  pair<long long, long long> x = calc(first.l, first.r, B);
  A /= g;
  second.l -= y0, second.r -= y0;
  pair<long long, long long> y = calc(second.l, second.r, A);
  y = make_pair(y.second * (-1), y.first * (-1));
  if (x.first > x.second || y.first > y.second) {
    cout << "0";
    exit(0);
  }
  if (x.second < y.first || y.second < x.first) return 0;
  return min(x.second, y.second) - max(x.first, y.first) + 1;
}
int main() {
  first.in(), second.in(), cin >> l >> r;
  first.calc_seg(l, r), second.calc_seg(l, r);
  cout << calc(first, second);
  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>
const long long MAX_N = (long long)1e5 + 123;
using namespace std;
pair<long long, long long> calc(long long L, long long R, long long a) {
  if (R >= 0)
    R /= a;
  else {
    if (R % a == 0)
      R /= a;
    else
      R = R / a - 1;
  }
  if (L >= 0) {
    if (L % a == 0)
      L /= a;
    else
      L = L / a + 1;
  } else
    L /= a;
  return make_pair(L, R);
}
struct num {
  long long a, b;
  long long l, r;
  void in() { cin >> a >> b; }
  void calc_seg(long long L, long long R) {
    pair<long long, long long> now = calc(L - b, R - b, a);
    l = max(now.first, 0ll), r = now.second;
    if (l > r) {
      cout << "0";
      exit(0);
    }
  }
} first, second;
long long l, r;
long long gcd(long long a, long long b, long long& x, long long& y) {
  if (a == 0) {
    x = 0;
    y = 1;
    return b;
  }
  long long x1, y1;
  long long d = gcd(b % a, a, x1, y1);
  x = y1 - (b / a) * x1;
  y = x1;
  return d;
}
bool find_any_solution(long long a, long long b, long long c, long long& x0,
                       long long& y0, long long& g) {
  g = gcd(abs(a), abs(b), x0, y0);
  if (c % g != 0) return false;
  x0 *= c / g;
  y0 *= c / g;
  if (a < 0) x0 *= -1;
  if (b < 0) y0 *= -1;
  return true;
}
long long calc(num first, num second) {
  long long A = first.a, B = -second.a, C = second.b - first.b;
  long long x0, y0, g;
  if (!find_any_solution(A, B, C, x0, y0, g)) {
    cout << "0";
    exit(0);
  }
  B /= g;
  first.l -= x0, first.r -= x0;
  first.l *= -1, first.r *= -1, B *= -1;
  swap(first.l, first.r);
  pair<long long, long long> x = calc(first.l, first.r, B);
  A /= g;
  second.l -= y0, second.r -= y0;
  pair<long long, long long> y = calc(second.l, second.r, A);
  y = make_pair(y.second * (-1), y.first * (-1));
  if (x.first > x.second || y.first > y.second) {
    cout << "0";
    exit(0);
  }
  if (x.second < y.first || y.second < x.first) return 0;
  return min(x.second, y.second) - max(x.first, y.first) + 1;
}
int main() {
  first.in(), second.in(), cin >> l >> r;
  first.calc_seg(l, r), second.calc_seg(l, r);
  cout << calc(first, second);
  return 0;
}

```