#include <bits/stdc++.h>
using namespace std;
long long a1, a2, b1, b2, L, R;
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, y, x);
  y -= x * (a / b);
  return r;
}
long long solve() {
  if (b1 > R || b2 > R) return 0;
  long long L1 = max(0LL, (L - b1 + a1 - 1) / a1);
  long long R1 = (R - b1) / a1;
  long long L2 = max(0LL, (L - b2 + a2 - 1) / a2);
  long long R2 = (R - b2) / a2;
  if (L1 > R1 || R1 < 0 || L2 > R2 || R2 < 0) return 0;
  long long A = a1, B = a2, C = b2 - b1;
  long long x, y, k;
  long long gcd = exgcd(A, B, x, y);
  y = -y;
  if (C % gcd) return 0;
  x *= C / gcd, y *= C / gcd;
  long long addx = B / gcd, addy = A / gcd;
  if (x < L1) {
    k = (L1 - x + addx - 1) / addx;
    x += k * addx;
    y += k * addy;
  }
  if (x > L1) {
    k = (x - L1) / addx;
    x -= k * addx;
    y -= k * addy;
  }
  if (y > R2) return 0;
  if (y < L2) {
    k = (L2 - y + addy - 1) / addy;
    x += k * addx;
    y += k * addy;
  }
  if (x >= L1 && x <= R1 && y >= L2 && y <= R2)
    return 1 + min((R1 - x) / addx, (R2 - y) / addy);
  else
    return 0;
}
int main() {
  cin >> a1 >> b1 >> a2 >> b2 >> L >> R;
  cout << solve();
  return 0;
}

### Prompt

Please formulate a cpp solution 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>
using namespace std;
long long a1, a2, b1, b2, L, R;
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, y, x);
  y -= x * (a / b);
  return r;
}
long long solve() {
  if (b1 > R || b2 > R) return 0;
  long long L1 = max(0LL, (L - b1 + a1 - 1) / a1);
  long long R1 = (R - b1) / a1;
  long long L2 = max(0LL, (L - b2 + a2 - 1) / a2);
  long long R2 = (R - b2) / a2;
  if (L1 > R1 || R1 < 0 || L2 > R2 || R2 < 0) return 0;
  long long A = a1, B = a2, C = b2 - b1;
  long long x, y, k;
  long long gcd = exgcd(A, B, x, y);
  y = -y;
  if (C % gcd) return 0;
  x *= C / gcd, y *= C / gcd;
  long long addx = B / gcd, addy = A / gcd;
  if (x < L1) {
    k = (L1 - x + addx - 1) / addx;
    x += k * addx;
    y += k * addy;
  }
  if (x > L1) {
    k = (x - L1) / addx;
    x -= k * addx;
    y -= k * addy;
  }
  if (y > R2) return 0;
  if (y < L2) {
    k = (L2 - y + addy - 1) / addy;
    x += k * addx;
    y += k * addy;
  }
  if (x >= L1 && x <= R1 && y >= L2 && y <= R2)
    return 1 + min((R1 - x) / addx, (R2 - y) / addy);
  else
    return 0;
}
int main() {
  cin >> a1 >> b1 >> a2 >> b2 >> L >> R;
  cout << solve();
  return 0;
}

```