P2152

#include <bits/stdc++.h>
using namespace std;
int a[10005],b[10005],d[10005];
int c[10005],e[10005],p[10005];
int lena,lenb,lend;
void divide() { //给 a 数组/2
	for(int i=1; i<=lena; i++) {
		if(a[i]&1==0) a[i]>>=1;
		else {
			if(a[i]<=1) {
				a[i+1]+=(a[i]*10);
				a[i]=0;
			} else {
				a[i+1]+=((a[i]%2)*10);
				a[i]>>=1;
			}
		}
	}
	if(a[1]==0) {
		for(int i=1; i<=lena-1; i++) a[i]=a[i+1];
		lena--;
	}
}
void divide1() { //给 b 数组/2
	for(int i=1; i<=lenb; i++) {
		if(b[i]&1==0) b[i]>>=1;
		else {
			if(b[i]<=1) {
				b[i+1]+=(b[i]*10);
				b[i]=0;
			} else {
				b[i+1]+=((b[i]%2)*10);
				b[i]>>=1;
			}
		}
	}
	if(b[1]==0) {
		for(int i=1; i<=lenb-1; i++) b[i]=b[i+1];
		lenb--;
	}
}
int bigger(int a[],int b[]) {
	//if a[] is bigger,return 1;
	//else if b[] is bigger,return 2;
	//The same,return 3;
	if(lena>lenb) return 1;
	else if(lenb>lena) return 2;
	else {
		for(int i=1; i<=lena; i++) {
			if(a[i]>b[i]) return 1;
			else if(a[i]<b[i]) return 2;
		}
		return 3;
	}
}
void Swap() {
	int mx;
	if(lena>lenb) mx=lena;
	else mx=lenb;
	for(int i=1; i<=mx; i++) {
		a[i]^=b[i];
		b[i]^=a[i];
		a[i]^=b[i];
	}
	lena^=lenb;
	lenb^=lena;
	lena^=lenb;
}
void pow2(int k) { //pow(2,k) memoried in d[]
	lend=1;
	if(k==0) {
		d[1]=1;
		return;
	}
	d[1]=2;
	for(int i=2; i<=k; i++) {
		for(int j=1; j<=lend; j++) d[j]<<=1;
		for(int j=1; j<=lend; j++) {
			if(d[j]>=10) {
				d[j+1]+=(d[j]/10);
				d[j]%=10;
				if(j==lend) {
					lend++;
					break;
				}
			}
		}
	}
	for(int i=1; i<=lend; i++) c[i]=d[lend-i+1];
	for(int i=1; i<=lend; i++) d[i]=c[i];
	memset(c,0,sizeof(c));
}
void high_precision_mul() { //a[] * pow(2,k)
	for(int i=1; i<=lena; i++) e[i]=a[lena-i+1];
	for(int i=1; i<=lend; i++) c[i]=d[lend-i+1];
	int g=0;
	int len3;
	for(int i=1; i<=lena; i++) {
		int s=0;
		for(int j=1; j<=lend; j++) {
			p[i+j-1]+=(e[i]*c[j]+s);
			s=p[i+j-1]/10;
			p[i+j-1]%=10;
		}
		p[i+lend]=s;
	}
	for(int i=10004; i>=1; i--) {
		if(p[i]!=0) {
			len3=i;
			break;
		}
		if(i==1) len3=i;
	}
	for(int i=len3; i>=1; i--) putchar_unlocked(p[i]+'0');
}
void high_precision_min() {//a[] - b[]
	for(int i=lenb; i>=1; i--) b[i+lena-lenb]=b[i];
	for(int i=1; i<=lena-lenb; i++) b[i]=0;
	for(int i=lena; i>=1; i--) {
		a[i]=a[i]-b[i];
		if(a[i]<0) {
			a[i]+=10;
			a[i-1]--;
		}
	}
	int tp=0;
	for(int i=1; i<=10004; i++) {
		if(a[i]!=0) {
			tp=i;
			break;
		}
	}
	for(int i=lena-lenb+1; i<=lena; i++) b[i-lena+lenb]=b[i];
	for(int i=lenb+1; i<=lena; i++) b[i]=0;
	for(int j=tp; j<=lena; j++) a[j-tp+1]=a[j];
	lena-=(tp-1);
}
void gcd() {
	int x=0,y=0;
	if(a[1]==0) {
		for(int i=1; i<=lenb; i++) cout<<b[i];
		exit(0);
	}
	if(b[1]==0) {
		for(int i=1; i<=lena; i++) cout<<a[i];
		exit(0);
	}
	while(1) {
		if(a[lena]&1==1) break;
		divide();
		x++;
	}
	while(1) {
		if(b[lenb]&1==1) break;
		divide1();
		y++;
	}
	if(y<x) x=y;
	while(1) {
		if(bigger(a,b)==3) {
			pow2(x);
			high_precision_mul();
			exit(0);
		}
		if(bigger(a,b)==2) Swap();
		high_precision_min();
		while(1) {
			if(a[lena]&1==1) break;
			divide();
		}
	}
}
main() {
	string a1,b1;
	while(1) {
		char c=getchar_unlocked();
		if(c=='\n') break;
		a1+=c;
		lena++;
	}
	while(1) {
		char c=getchar_unlocked();
		if(c=='\n') break;
		b1+=c;
		lenb++;
	}
	for(int i=0; i<lena; i++) a[i+1]=(a1[i]-'0');
	for(int i=0; i<lenb; i++) b[i+1]=(b1[i]-'0');
	gcd();
}