#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


ll M,N,A,B,C,D;

ll extgcd(ll a,ll b,ll &x,ll &y){
	ll d = a;
	if(b != 0){
		d = extgcd(b,a%b,y,x);
		y -= (a/b)*x;
	}else{
		x = 1;
		y = 0;
	}
	return d;
}

ll mod_inverse(ll a,ll m){
	ll x,y;
	extgcd(a,m,x,y);
	return (m+x%m)%m;
}

ll gcd(ll x,ll y){
	if(x < y){
		swap(x,y);
	}
	if(y == 0){
		return x;
	}else{
		return gcd(y,x%y);
	}
}

ll lcm(ll x,ll y){

	return (x*y)/gcd(x,y);
}

int main(){

	scanf("%lld %lld %lld %lld %lld %lld",&M,&N,&A,&B,&C,&D);

	ll e = lcm(M/gcd(A,M),N/gcd(B,N));

	vector<ll> V;

	for(ll i = 1; i*i <= M*N; i++){
		if((M*N)%i != 0)continue;

		V.push_back(i);
		V.push_back((M*N)/i);
	}

	sort(V.begin(),V.end());

	for(int i = 0; i < V.size(); i++){

		ll f = V[i];

		if(f*C%gcd(A,M) != 0 || f*D%gcd(B,N) != 0)continue;

		ll L = (f*C/gcd(A,M))*mod_inverse(A/gcd(A,M),M/gcd(A,M));
		ll R = (f*D/gcd(B,N))*mod_inverse(B/gcd(B,N),N/gcd(B,N));
		ll tmp_mod = gcd(M/gcd(A,M),N/gcd(B,N));

		if(L%tmp_mod == R%tmp_mod){

			printf("%lld\n",e*f-1);
			return 0;
		}
	}

	return 0;
}


### Prompt

Please create a solution in CPP to the following problem:

There is a board of m × n squares. The squares of i rows and j columns are represented by (i, j) (0 ≤ i <m, 0 ≤ j <n).

When the rabbit is at (x, y), it can jump to ((x + a) mod m, (y + b) mod n) or ((x + c) mod m, (y + d) mod n) it can.

Now the rabbit is at (0, 0). If you can't go back to the square that once jumped, how many times can the rabbit jump?



Input

Input is given with m, n, a, b, c, d separated by spaces on one line. 1 ≤ m, n, a, b, c, d ≤ 100 000

Output

Output the maximum number of times the rabbit can jump in one line.

Example

Input

6 6 2 2 2 4


Output

8

### Response

```cpp
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


ll M,N,A,B,C,D;

ll extgcd(ll a,ll b,ll &x,ll &y){
	ll d = a;
	if(b != 0){
		d = extgcd(b,a%b,y,x);
		y -= (a/b)*x;
	}else{
		x = 1;
		y = 0;
	}
	return d;
}

ll mod_inverse(ll a,ll m){
	ll x,y;
	extgcd(a,m,x,y);
	return (m+x%m)%m;
}

ll gcd(ll x,ll y){
	if(x < y){
		swap(x,y);
	}
	if(y == 0){
		return x;
	}else{
		return gcd(y,x%y);
	}
}

ll lcm(ll x,ll y){

	return (x*y)/gcd(x,y);
}

int main(){

	scanf("%lld %lld %lld %lld %lld %lld",&M,&N,&A,&B,&C,&D);

	ll e = lcm(M/gcd(A,M),N/gcd(B,N));

	vector<ll> V;

	for(ll i = 1; i*i <= M*N; i++){
		if((M*N)%i != 0)continue;

		V.push_back(i);
		V.push_back((M*N)/i);
	}

	sort(V.begin(),V.end());

	for(int i = 0; i < V.size(); i++){

		ll f = V[i];

		if(f*C%gcd(A,M) != 0 || f*D%gcd(B,N) != 0)continue;

		ll L = (f*C/gcd(A,M))*mod_inverse(A/gcd(A,M),M/gcd(A,M));
		ll R = (f*D/gcd(B,N))*mod_inverse(B/gcd(B,N),N/gcd(B,N));
		ll tmp_mod = gcd(M/gcd(A,M),N/gcd(B,N));

		if(L%tmp_mod == R%tmp_mod){

			printf("%lld\n",e*f-1);
			return 0;
		}
	}

	return 0;
}


```