#include <bits/stdc++.h>
void egcd(long long greater, long long lesser, long long *d, long long *x,
          long long *y) {
  long long tx, ty;
  if (lesser == 0) {
    *d = greater;
    *x = 1;
    *y = 0;
    return;
  }
  egcd(lesser, greater % lesser, d, x, y);
  tx = *y;
  ty = *x - (greater / lesser) * (*y);
  *x = tx;
  *y = ty;
}
long long gcd(long greater, long lesser) {
  if (greater % lesser == 0) return lesser;
  return gcd(lesser, greater % lesser);
}
long long left, right, a1, a2, b1, b2;
int main(void) {
  long long delta, lefti, righti;
  long long d, c1, c2;
  double left0, right0, right1, right2, right3;
  scanf("%lld%lld%lld%lld%lld%lld", &a1, &b1, &a2, &b2, &left, &right);
  if (a2 >= a1)
    egcd(a2, a1, &d, &c2, &c1);
  else
    egcd(a1, a2, &d, &c1, &c2);
  delta = b2 - b1;
  if (delta % d) {
    printf("0\n");
    return 0;
  }
  right1 = 1.0 * delta * c1 / a2;
  right2 = -1.0 * delta * c2 / a1;
  left0 = 1.0 * delta * c1 / a2 - 1.0 * d * (right - b1) / (1.0 * a1 * a2);
  right3 = 1.0 * delta * c1 / a2 - 1.0 * d * (left - b1) / (1.0 * a1 * a2);
  right0 = right1 < right2 ? right1 : right2;
  right0 = right0 < right3 ? right0 : right3;
  lefti = (long long)left0;
  if (left0 > 0 && lefti != left0) lefti += 1;
  righti = (long long)right0;
  if (right0 < 0 && righti != right0) righti -= 1;
  printf("%lld\n", lefti > righti ? 0 : righti - lefti + 1);
  return 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>
void egcd(long long greater, long long lesser, long long *d, long long *x,
          long long *y) {
  long long tx, ty;
  if (lesser == 0) {
    *d = greater;
    *x = 1;
    *y = 0;
    return;
  }
  egcd(lesser, greater % lesser, d, x, y);
  tx = *y;
  ty = *x - (greater / lesser) * (*y);
  *x = tx;
  *y = ty;
}
long long gcd(long greater, long lesser) {
  if (greater % lesser == 0) return lesser;
  return gcd(lesser, greater % lesser);
}
long long left, right, a1, a2, b1, b2;
int main(void) {
  long long delta, lefti, righti;
  long long d, c1, c2;
  double left0, right0, right1, right2, right3;
  scanf("%lld%lld%lld%lld%lld%lld", &a1, &b1, &a2, &b2, &left, &right);
  if (a2 >= a1)
    egcd(a2, a1, &d, &c2, &c1);
  else
    egcd(a1, a2, &d, &c1, &c2);
  delta = b2 - b1;
  if (delta % d) {
    printf("0\n");
    return 0;
  }
  right1 = 1.0 * delta * c1 / a2;
  right2 = -1.0 * delta * c2 / a1;
  left0 = 1.0 * delta * c1 / a2 - 1.0 * d * (right - b1) / (1.0 * a1 * a2);
  right3 = 1.0 * delta * c1 / a2 - 1.0 * d * (left - b1) / (1.0 * a1 * a2);
  right0 = right1 < right2 ? right1 : right2;
  right0 = right0 < right3 ? right0 : right3;
  lefti = (long long)left0;
  if (left0 > 0 && lefti != left0) lefti += 1;
  righti = (long long)right0;
  if (right0 < 0 && righti != right0) righti -= 1;
  printf("%lld\n", lefti > righti ? 0 : righti - lefti + 1);
  return 0;
}

```