#include<bits/stdc++.h>
using namespace std;
struct node{
	int a[100001];
	int len;
}A,B;
string s1,s2;
void print(node x){
	for(int i=x.len-1;i>=0;i--)
		cout<<x.a[i];
	return;
}
node div(node x){
	for(int i=x.len-1;i>=1;i--){
		x.a[i-1]+=(x.a[i]%2)*10;
		x.a[i]/=2;
	}
	x.a[0]/=2;
	if(x.a[x.len-1]==0) x.len--;
	return x; 
}
node cheng2(node x){
	x.a[0]*=2;
	for(int i=1;i<=x.len;i++){
		x.a[i]*=2;
		x.a[i]+=(x.a[i-1]/10);
		x.a[i-1]%=10;
	}
	if(x.a[x.len]) x.len++;
	return x;
}
int da(node x,node y){
	if(x.len>y.len) return 1;
	if(x.len<y.len) return 0;
	for(int i=x.len-1;i>=0;i--){
		if(x.a[i]>y.a[i]) return 1;
		if(x.a[i]<y.a[i]) return 0;
	}
	return 0;
}
node jian(node x,node y){
	for(int i=0;i<y.len;i++){
		if(x.a[i]>=y.a[i]) x.a[i]-=y.a[i];
		else{
			x.a[i]+=10;
			x.a[i+1]--;
			x.a[i]-=y.a[i];
		}
	}
	if(x.a[x.len-1]==0) x.len--;
	return x;
}
node GCD(node x,node y){
	cout<<1;
	if(x.a[0]==0&&x.len==1) return y;
	if(y.a[0]==0&&y.len==1) return x;
	if((x.a[0]%2==0)&&(y.a[0]%2==0)) {
		print(x);print(y);
		return cheng2(GCD(div(x),div(y)));
	}
	if((x.a[0]%2==1)&&(y.a[0]%2==0)) return GCD(x,div(y));
	if((x.a[0]%2==0)&&(y.a[0]%2==1)) return GCD(div(x),y);
	if((x.a[0]%2==1)&&(y.a[0]%2==1)){
		print(x);print(y);
		if(da(x,y))
			return GCD(jian(x,y),y);
		else
			return GCD(jian(y,x),x);
	}
}
int main(){
	cin>>s1>>s2;
	A.len=s1.size();B.len=s2.size();
	for(int i=0;i<A.len;i++)
		A.a[A.len-i-1]=s1[i]-'0';
	for(int i=0;i<B.len;i++)
		B.a[B.len-i-1]=s2[i]-'0';
	node C=GCD(A,B);
	print(C);
	return 0;
}

心态已经崩掉，不知道为啥会MLE。