#include <bits/stdc++.h>
using namespace std;
long long x, y;
long long gcdEx(long long a, long long b) {
  if (a == 0) {
    x = 0;
    y = 1;
    return b;
  }
  long long ans = gcdEx(b % a, a);
  long long temX = x;
  long long temY = y;
  x = temY - (b / a) * temX;
  y = temX;
  return ans;
}
long long up(long long, long long);
long long down(long long a, long long b) {
  if (b < 0) return down(-a, -b);
  if (a < 0) return -up(-a, b);
  return a / b;
}
long long up(long long a, long long b) {
  if (b < 0) return up(-a, -b);
  if (a < 0) return -down(-a, b);
  return (a + b - 1) / b;
}
long long a1, a2, b1, b2;
long long l, r;
int main() {
  cin >> a1 >> b1 >> a2 >> b2 >> l >> r;
  l = max(0ll, up(l - b1, a1));
  r = down(r - b1, a1);
  long long a = a1;
  long long b = -a2;
  long long c = b2 - b1;
  long long g = gcdEx(a, b);
  if (c % g != 0 || l > r) {
    cout << "0" << endl;
    return 0;
  }
  if (g < 0) {
    g = -g;
    x = -x;
    y = -y;
  }
  long long sta = up(r * g - x * c, b);
  long long sto = down(l * g - x * c, b);
  sto = min(sto, down(y * c, a));
  cout << max(0ll, sto - sta + 1) << endl;
}

### Prompt

In Cpp, your task is to solve 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 x, y;
long long gcdEx(long long a, long long b) {
  if (a == 0) {
    x = 0;
    y = 1;
    return b;
  }
  long long ans = gcdEx(b % a, a);
  long long temX = x;
  long long temY = y;
  x = temY - (b / a) * temX;
  y = temX;
  return ans;
}
long long up(long long, long long);
long long down(long long a, long long b) {
  if (b < 0) return down(-a, -b);
  if (a < 0) return -up(-a, b);
  return a / b;
}
long long up(long long a, long long b) {
  if (b < 0) return up(-a, -b);
  if (a < 0) return -down(-a, b);
  return (a + b - 1) / b;
}
long long a1, a2, b1, b2;
long long l, r;
int main() {
  cin >> a1 >> b1 >> a2 >> b2 >> l >> r;
  l = max(0ll, up(l - b1, a1));
  r = down(r - b1, a1);
  long long a = a1;
  long long b = -a2;
  long long c = b2 - b1;
  long long g = gcdEx(a, b);
  if (c % g != 0 || l > r) {
    cout << "0" << endl;
    return 0;
  }
  if (g < 0) {
    g = -g;
    x = -x;
    y = -y;
  }
  long long sta = up(r * g - x * c, b);
  long long sto = down(l * g - x * c, b);
  sto = min(sto, down(y * c, a));
  cout << max(0ll, sto - sta + 1) << endl;
}

```