#include <bits/stdc++.h>
using namespace std;
const int MX = 1e3 + 5;
int n;
long long m[MX], r[MX];
long long exgcd(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long r = exgcd(b, a % b, x, y);
  long long t = y;
  y = x - a / b * y;
  x = t;
  return r;
}
pair<long long, long long> ex_crt() {
  long long M = m[1], R = r[1], x, y, d;
  for (int i = 2; i <= n; i++) {
    d = exgcd(M, m[i], x, y);
    if ((r[i] - R) % d) return make_pair(-1, -1);
    x = (r[i] - R) / d * x % (m[i] / d);
    R = R + x * M;
    M = M / d * m[i];
    R %= M;
  }
  R = R > 0 ? R : R + M;
  return make_pair(R, M);
}
int main() {
  long long L, R;
  n = 2;
  for (int i = 1; i <= n; i++) {
    scanf("%I64d%I64d", &m[i], &r[i]);
  }
  scanf("%I64d%I64d", &L, &R);
  pair<long long, long long> ans = ex_crt();
  L = max(L, max(r[1], r[2]));
  if (ans.first == -1 || L > R) {
    printf("0\n");
  } else {
    long long B = ans.first, M = ans.second, ans;
    if (M > 0) {
      ans = floor((double)(R - B) / M) - floor((double)(L - B) / M);
      if ((L - B) % M == 0) ans++;
    } else {
      ans = floor((double)(L - B) / M) - floor((double)(R - B) / M);
      if ((R - B) % M == 0) ans++;
    }
    printf("%I64d\n", ans);
  }
  return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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 int MX = 1e3 + 5;
int n;
long long m[MX], r[MX];
long long exgcd(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long r = exgcd(b, a % b, x, y);
  long long t = y;
  y = x - a / b * y;
  x = t;
  return r;
}
pair<long long, long long> ex_crt() {
  long long M = m[1], R = r[1], x, y, d;
  for (int i = 2; i <= n; i++) {
    d = exgcd(M, m[i], x, y);
    if ((r[i] - R) % d) return make_pair(-1, -1);
    x = (r[i] - R) / d * x % (m[i] / d);
    R = R + x * M;
    M = M / d * m[i];
    R %= M;
  }
  R = R > 0 ? R : R + M;
  return make_pair(R, M);
}
int main() {
  long long L, R;
  n = 2;
  for (int i = 1; i <= n; i++) {
    scanf("%I64d%I64d", &m[i], &r[i]);
  }
  scanf("%I64d%I64d", &L, &R);
  pair<long long, long long> ans = ex_crt();
  L = max(L, max(r[1], r[2]));
  if (ans.first == -1 || L > R) {
    printf("0\n");
  } else {
    long long B = ans.first, M = ans.second, ans;
    if (M > 0) {
      ans = floor((double)(R - B) / M) - floor((double)(L - B) / M);
      if ((L - B) % M == 0) ans++;
    } else {
      ans = floor((double)(L - B) / M) - floor((double)(R - B) / M);
      if ((R - B) % M == 0) ans++;
    }
    printf("%I64d\n", ans);
  }
  return 0;
}

```