#include <bits/stdc++.h>
using namespace std;
long long exgcd(long long m, long long &x, long long n, long long &y) {
  long long x1 = 0, y1 = 1, x0 = 1, y0 = 0;
  long long r = (m % n + n) % n;
  long long q = (m - r) / n;
  x = 0, y = 1;
  while (r) {
    x = x0 - q * x1;
    y = y0 - q * y1;
    x0 = x1;
    y0 = y1;
    x1 = x;
    y1 = y;
    m = n;
    n = r;
    r = m % n;
    q = (m - r) / n;
  }
  return n;
}
int main() {
  long long a1, r1, ai, ri, l, r;
  while (cin >> a1 >> r1 >> ai >> ri >> l >> r) {
    if ((r - r1) / a1 < 0 || (r - ri) / ai < 0) {
      printf("0\n");
      continue;
    }
    if ((l - r1) / a1 < 0) l = r1;
    if ((l - ri) / ai < 0) l = ri;
    bool flag = true;
    long long a, b;
    long long gcd = exgcd(a1, a, ai, b);
    if ((ri - r1) % gcd)
      flag = false;
    else {
      long long t = ai / gcd;
      a = ((ri - r1) / gcd * a % t + t) % t;
      r1 = a * a1 + r1;
      a1 = a1 * (ai / gcd);
    }
    if (!flag)
      printf("0\n");
    else {
      long long memo = (l - r1 + a1 - 1) / a1;
      memo = r1 + memo * a1;
      if (memo > r) {
        printf("0\n");
        continue;
      } else
        cout << (r - memo) / a1 + 1 << endl;
    }
  }
  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 exgcd(long long m, long long &x, long long n, long long &y) {
  long long x1 = 0, y1 = 1, x0 = 1, y0 = 0;
  long long r = (m % n + n) % n;
  long long q = (m - r) / n;
  x = 0, y = 1;
  while (r) {
    x = x0 - q * x1;
    y = y0 - q * y1;
    x0 = x1;
    y0 = y1;
    x1 = x;
    y1 = y;
    m = n;
    n = r;
    r = m % n;
    q = (m - r) / n;
  }
  return n;
}
int main() {
  long long a1, r1, ai, ri, l, r;
  while (cin >> a1 >> r1 >> ai >> ri >> l >> r) {
    if ((r - r1) / a1 < 0 || (r - ri) / ai < 0) {
      printf("0\n");
      continue;
    }
    if ((l - r1) / a1 < 0) l = r1;
    if ((l - ri) / ai < 0) l = ri;
    bool flag = true;
    long long a, b;
    long long gcd = exgcd(a1, a, ai, b);
    if ((ri - r1) % gcd)
      flag = false;
    else {
      long long t = ai / gcd;
      a = ((ri - r1) / gcd * a % t + t) % t;
      r1 = a * a1 + r1;
      a1 = a1 * (ai / gcd);
    }
    if (!flag)
      printf("0\n");
    else {
      long long memo = (l - r1 + a1 - 1) / a1;
      memo = r1 + memo * a1;
      if (memo > r) {
        printf("0\n");
        continue;
      } else
        cout << (r - memo) / a1 + 1 << endl;
    }
  }
  return 0;
}

```