#include <bits/stdc++.h>
using namespace std;
const long long mx = 2e9;
long long x, y, p, q, l, r, d, z;
long long gcd(long long x, long long y) { return y ? gcd(y, x % y) : x; }
long long qow(long long x, long long y, long long p) {
  return y ? (y & 1 ? x * qow(x, y - 1, p) % p : qow(x * x % p, y / 2, p)) : 1;
}
long long F(long long n, long long k) {
  if (k * x * d + y > n) return 0;
  long long z = (n - y) / (x * d);
  return ((n - y) / (x * d) - k) / p + 1;
}
long long phi(long long n) {
  long long res = n;
  for (long long i = 2; i * i <= n; i++)
    if (n % i == 0) {
      res /= i, res *= i - 1;
      while (n % i == 0) n /= i;
    }
  if (n > 1) res /= n, res *= n - 1;
  return res;
}
int main() {
  cin >> x >> y >> p >> q >> l >> r;
  y += mx, q += mx, l += mx, r += mx;
  if (q >= y) swap(x, p), swap(y, q);
  z = (q - y) % p, (z += p) %= p;
  d = gcd(x, p), x /= d, p /= d;
  if (z % d) return printf("0\n"), 0;
  z /= d;
  long long k = p > 1 ? z * qow(x, phi(p) - 1, p) % p : 0;
  return printf("%I64d\n", F(r, k) - F(l - 1, k)), 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>
using namespace std;
const long long mx = 2e9;
long long x, y, p, q, l, r, d, z;
long long gcd(long long x, long long y) { return y ? gcd(y, x % y) : x; }
long long qow(long long x, long long y, long long p) {
  return y ? (y & 1 ? x * qow(x, y - 1, p) % p : qow(x * x % p, y / 2, p)) : 1;
}
long long F(long long n, long long k) {
  if (k * x * d + y > n) return 0;
  long long z = (n - y) / (x * d);
  return ((n - y) / (x * d) - k) / p + 1;
}
long long phi(long long n) {
  long long res = n;
  for (long long i = 2; i * i <= n; i++)
    if (n % i == 0) {
      res /= i, res *= i - 1;
      while (n % i == 0) n /= i;
    }
  if (n > 1) res /= n, res *= n - 1;
  return res;
}
int main() {
  cin >> x >> y >> p >> q >> l >> r;
  y += mx, q += mx, l += mx, r += mx;
  if (q >= y) swap(x, p), swap(y, q);
  z = (q - y) % p, (z += p) %= p;
  d = gcd(x, p), x /= d, p /= d;
  if (z % d) return printf("0\n"), 0;
  z /= d;
  long long k = p > 1 ? z * qow(x, phi(p) - 1, p) % p : 0;
  return printf("%I64d\n", F(r, k) - F(l - 1, k)), 0;
}

```