#include <bits/stdc++.h>
struct tri {
  long long d, x, y;
  tri() {}
  tri(long long dd, long long xx, long long yy) : d(dd), x(xx), y(yy) {}
};
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
tri exgcd(long long a, long long b) {
  if (b == 0) return tri(a, 1, 0);
  tri pans = exgcd(b, a % b);
  return tri(pans.d, pans.y, pans.x - (a / b) * pans.y);
}
long long mul(long long a, long long b, long long p) {
  a = ((a % p) + p) % p;
  b = ((b % p) + p) % p;
  long long ret = 0;
  for (; b; b >>= 1, a = (a + a) % p)
    if (b & 1) ret = (ret + a) % p;
  return ret;
}
long long crd(long long a1, long long a2, long long &m1, long long &m2) {
  tri pans = exgcd(m1, m2);
  long long C = a2 - a1;
  long long mod = m2 / pans.d;
  pans.x = mul(pans.x, C / pans.d, mod);
  mod *= m1;
  a1 += mul(m1, pans.x, mod);
  m1 = mod / m2;
  return a1;
}
long long fix(long long x, long long p, long long mod) {
  long long pp = p - x;
  pp /= mod;
  x += pp * mod;
  while (x - p > mod) x -= mod;
  while (p - x > 0) x += mod;
  return x;
}
long long findd(long long x, long long l, long long r, long long mod) {
  if (r < x) return 0;
  long long ans = 1;
  long long p = r - x;
  p /= mod;
  ans += p;
  x += p * mod;
  while (r - x >= mod) {
    x += mod;
    ans++;
  }
  while (x - r > 0) {
    x -= mod;
    ans--;
  }
  return ans;
}
int main() {
  long long a1, b1, a2, b2, l, r;
  while (scanf("%lld%lld%lld%lld%lld%lld", &a1, &b1, &a2, &b2, &l, &r) == 6) {
    long long abp = b1 - b2;
    if (abp < 0) abp = -abp;
    if (abp % gcd(a1, a2) != 0) {
      printf("0\n");
      continue;
    }
    long long x = crd(b1, b2, a1, a2);
    long long p = b1, mod = a1;
    if (p < b2) p = b2;
    if (p < l) p = l;
    mod *= a2;
    x = fix(x, p, mod);
    long long ans = findd(x, l, r, mod);
    printf("%lld\n", ans);
  }
}

### 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>
struct tri {
  long long d, x, y;
  tri() {}
  tri(long long dd, long long xx, long long yy) : d(dd), x(xx), y(yy) {}
};
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
tri exgcd(long long a, long long b) {
  if (b == 0) return tri(a, 1, 0);
  tri pans = exgcd(b, a % b);
  return tri(pans.d, pans.y, pans.x - (a / b) * pans.y);
}
long long mul(long long a, long long b, long long p) {
  a = ((a % p) + p) % p;
  b = ((b % p) + p) % p;
  long long ret = 0;
  for (; b; b >>= 1, a = (a + a) % p)
    if (b & 1) ret = (ret + a) % p;
  return ret;
}
long long crd(long long a1, long long a2, long long &m1, long long &m2) {
  tri pans = exgcd(m1, m2);
  long long C = a2 - a1;
  long long mod = m2 / pans.d;
  pans.x = mul(pans.x, C / pans.d, mod);
  mod *= m1;
  a1 += mul(m1, pans.x, mod);
  m1 = mod / m2;
  return a1;
}
long long fix(long long x, long long p, long long mod) {
  long long pp = p - x;
  pp /= mod;
  x += pp * mod;
  while (x - p > mod) x -= mod;
  while (p - x > 0) x += mod;
  return x;
}
long long findd(long long x, long long l, long long r, long long mod) {
  if (r < x) return 0;
  long long ans = 1;
  long long p = r - x;
  p /= mod;
  ans += p;
  x += p * mod;
  while (r - x >= mod) {
    x += mod;
    ans++;
  }
  while (x - r > 0) {
    x -= mod;
    ans--;
  }
  return ans;
}
int main() {
  long long a1, b1, a2, b2, l, r;
  while (scanf("%lld%lld%lld%lld%lld%lld", &a1, &b1, &a2, &b2, &l, &r) == 6) {
    long long abp = b1 - b2;
    if (abp < 0) abp = -abp;
    if (abp % gcd(a1, a2) != 0) {
      printf("0\n");
      continue;
    }
    long long x = crd(b1, b2, a1, a2);
    long long p = b1, mod = a1;
    if (p < b2) p = b2;
    if (p < l) p = l;
    mod *= a2;
    x = fix(x, p, mod);
    long long ans = findd(x, l, r, mod);
    printf("%lld\n", ans);
  }
}

```