#include <bits/stdc++.h>
using namespace std;
long long quo_floor(long long x, long long y) {
  return (x < 0) ^ (y < 0) ? -(abs(x) + abs(y) - 1) / abs(y) : x / y;
}
long long quo_ceil(long long x, long long y) {
  return (x < 0) ^ (y < 0) ? -abs(x) / abs(y) : (x + y - 1) / y;
}
long long exgcd(long long a, long long b, long long &x, long long &y) {
  if (!b) return x = 1, y = 0, a;
  long long d = exgcd(b, a % b, y, x);
  return y -= a / b * x, d;
}
long long a1, a2, b1, b2, l, r;
signed main() {
  cin >> a1 >> b1 >> a2 >> b2 >> l >> r;
  long long x, y, gcd = exgcd(a1, -a2, x, y);
  if ((b2 - b1) % gcd) return puts("0"), 0;
  x *= (b2 - b1) / gcd;
  y *= (b2 - b1) / gcd;
  long long dx = abs(a2 / gcd), dy = abs(a1 / gcd);
  ((x %= dx) += dx) %= dx;
  y = (a1 * x - (b2 - b1)) / a2;
  if (y < 0) ((y %= dy) += dy) %= dy, x = (a2 * y + (b2 - b1)) / a1;
  long long l0 = max(0ll, quo_ceil(l - a1 * x - b1, a1 * dx)),
            r0 = quo_floor(r - a1 * x - b1, a1 * dx);
  cout << max(0ll, r0 - l0 + 1);
  return 0;
}

### Prompt

Create a solution in Cpp for 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;
long long quo_floor(long long x, long long y) {
  return (x < 0) ^ (y < 0) ? -(abs(x) + abs(y) - 1) / abs(y) : x / y;
}
long long quo_ceil(long long x, long long y) {
  return (x < 0) ^ (y < 0) ? -abs(x) / abs(y) : (x + y - 1) / y;
}
long long exgcd(long long a, long long b, long long &x, long long &y) {
  if (!b) return x = 1, y = 0, a;
  long long d = exgcd(b, a % b, y, x);
  return y -= a / b * x, d;
}
long long a1, a2, b1, b2, l, r;
signed main() {
  cin >> a1 >> b1 >> a2 >> b2 >> l >> r;
  long long x, y, gcd = exgcd(a1, -a2, x, y);
  if ((b2 - b1) % gcd) return puts("0"), 0;
  x *= (b2 - b1) / gcd;
  y *= (b2 - b1) / gcd;
  long long dx = abs(a2 / gcd), dy = abs(a1 / gcd);
  ((x %= dx) += dx) %= dx;
  y = (a1 * x - (b2 - b1)) / a2;
  if (y < 0) ((y %= dy) += dy) %= dy, x = (a2 * y + (b2 - b1)) / a1;
  long long l0 = max(0ll, quo_ceil(l - a1 * x - b1, a1 * dx)),
            r0 = quo_floor(r - a1 * x - b1, a1 * dx);
  cout << max(0ll, r0 - l0 + 1);
  return 0;
}

```