You have two variables a and b. Consider the following sequence of actions performed with these variables:

  1. If a = 0 or b = 0, end the process. Otherwise, go to step 2;
  2. If a ≥ 2·b, then set the value of a to a - 2·b, and repeat step 1. Otherwise, go to step 3;
  3. If b ≥ 2·a, then set the value of b to b - 2·a, and repeat step 1. Otherwise, end the process.



Initially the values of a and b are positive integers, and so the process will be finite.

You have to determine the values of a and b after the process ends.

Input

The only line of the input contains two integers n and m (1 ≤ n, m ≤ 1018). n is the initial value of variable a, and m is the initial value of variable b.

Output

Print two integers — the values of a and b after the end of the process.

Examples

Input

12 5


Output

0 1


Input

31 12


Output

7 12

Note

Explanations to the samples:

  1. a = 12, b = 5 <image> a = 2, b = 5 <image> a = 2, b = 1 <image> a = 0, b = 1;
  2. a = 31, b = 12 <image> a = 7, b = 12.
'''
t= input()
lng= len(t)
li1=[]; li2=[]
for i in range(lng):
    if t[i]!='a':
        li1.append(t[i])
    elif t[i]=='a':
        li2.append(i)
        
aa= ''.join(li1)
if len(aa)==0:
    print(t); exit(0)
if len(aa)%2==1:
    print(':('); exit(0)
if len(aa)%2==0:
    #print(123)
    l= int(len(aa)/2); lp= l#; print(l)
    ll= aa[l:]; lll=aa[0:l] #; print(ll)
    if ll!=lll:
        print(':('); exit(0)
    if ll not in t:
        print(':('); exit(0)
    tp= t[::-1]; tc= ll[::-1]#; print(tp,tc)
    if tp.find(tc)!=0:
        print(':('); exit(0)
    if tp.find(tc)==0:
        ul= len(tc)
        lu= tp[ul:][::-1]
        print(lu); exit(0)
        
   '''
#print(ord("T")-ord('A')+1)
'''
def fk (a):
    if a=='ACTG':
        return 0
   # print(a)
    cv=0
   # cv+= min(abs(ord(a[0])-ord('A')), (ord('A')-ord('A')+1+ 26- ord(a[0])))
    cv+= (min(abs(ord(a[0])-ord('A')), (ord('A')-ord('A')+1+ 26- (ord(a[0])-ord('A')+1) ), (ord(a[0])-ord('A')+ abs(27- (ord("A")-ord('A')+1)) ) ))
    
   # cv+= min(abs(ord(a[1])-ord('C')), (ord('C')-ord('A')+1+ 26- ord(a[1])))
    cv+= (min(abs(ord(a[1])-ord('C')), (ord('C')-ord('A')+1+ 26- (ord(a[1])-ord('A')+1) ), (ord(a[1])-ord('A')+ abs(27- (ord("C")-ord('A')+1)) ) ))
    
    #cv+= min(abs(ord(a[2])-ord('T')), (ord('T')-ord('A')+1+ 26- ord(a[2])))#; print(abs(ord(a[2])-ord('T')), (ord('T')-ord('A')+1+ 26- ord(a[2])))
    cv+= (min(abs(ord(a[2])-ord('T')), (ord('T')-ord('A')+1+ 26- (ord(a[2])-ord('A')+1) ), (ord(a[2])-ord('A')+ abs(27- (ord("T")-ord('A')+1)) ) ))
    
    #cv+= min(abs(ord(a[3])-ord('G')), (ord('G')-ord('A')+1+ 26- ord(a[3])))
    cv+= (min(abs(ord(a[3])-ord('G')), (ord('G')-ord('A')+1+ 26- (ord(a[3])-ord('A')+1) ), (ord(a[3])-ord('A')+ abs(27- (ord("G")-ord('A')+1)) ) ))
    
    return cv

n= int(input()); s=input(); li=[]
for i in range(n-4+1):
    ab= s[i:i+4]
    li.append(fk(ab))
li.sort()
print(li[0])
'''
'''
n= int(input())
li= list(map(str, input().split())); li= li*2; li= ''.join(li); li= li.replace('0',' ')
li1= li.split()
try:
    print(len(max(li1)))
except:
    print(0)'''

'''
from math import *

def prmfct(n):
    li=[]
    while n%2==0:
        li.append(2)
        n= n/2
    for i in range(3,int(sqrt(n))+1,2):
        while n%i==0:
            li.append(int(i))
            n=int(n/i)
    if n>2:
        li.append(int(n))
        
        
    return li


n,m= input().split(); n,m= int(n), int(m)

if m%n!=0:
    print(-1)
else:
    lim= prmfct(int(m/n))
    li= list(set(lim))
    if len(li)==2 and li[0]==2 and li[1]==3:
        print(len(lim))
    elif len(li)==1 and (li[0]==2 or li[0]==3):
        print(len(lim))
    elif len(li)==0:
        print(0)
    else:
        print(-1)'''
'''
from math import *
a,b= input().split(); a,b= int(a), int(b)
print(factorial(min(a,b)))'''

#from math import *
#def fact(n):
#    li=[]
#    for i in range(1,int(sqrt(n))+1):
#        if n%i==0:
#            li.append(i)
#            if i!=n/i:
#                li.append(int(n/i))
#    li.sort()
#    return li
#
#n= int(input())
#li1= list(map(int, input().split()))
#ab= max(li1)
#li2= fact(ab)
#li3= list(i for i in li1 if i not in li2)
#li4= list(set(list(i for i in li1 if li1.count(i)==2)))
#li3.extend(li4)
#print(ab, max(li3))





## A Python program to print all  
## permutations of given length 
#from itertools import permutations 
#  
## Get all permutations of length 2 
## and length 2 
#perm = permutations([1, 2, 3,4,5,6,7,8,9,0], 4) 
#j=1
## Print the obtained permutations 
#for i in list(perm):
#    li= list(i)
#    li[0]=str(li[0]); li[1]=str(li[1]); li[2]=str(li[2]); li[3]=str(li[3])
#    ab= ''.join(li)
#    print(str(j)+' ' 'Kornopuli'+ab); j+=1



#n= int(input()); li1= list(map(int, input().split())); li3=[]; baal_falan=0
#if n==1:
#    if li1[0]==0:
#        print(0); exit(0)
#    else:
#        print(1); exit(0)
#
#for i in range(n):
#    if li1[i]==1:
#        li3.append(1)
#    else:
#        if i==0:
#            baal_falan=1
#        elif i==n-1:
#            baal_falan=1
#        else:
#            if li1[i+1]==0 or li1[i-1]==0:
#                baal_falan=1
#            else:
#                li3.append(1)
#                
#print(len(li3))

#n= int(input()); s= input(); s= s+'0'; li= list(s); baal_falan=0; cn=0; sv=['R','G','B']
#for i in range(n):
#    if li[i]!=li[i+1]:
#        baal_falan=1
#    else:
#        cn+=1
#        if sv[0]!=li[i] and sv[0]!=li[i+2]:
#            li[i+1]= sv[0]
#        elif sv[1]!=li[i] and sv[1]!=li[i+2]:
#            li[i+1]= sv[1]
#        elif sv[2]!=li[i] and sv[2]!=li[i+2]:
#            li[i+1]= sv[2]
#print(cn); print(''.join(li[0:n]))


#li=[1,5,8,7,4,6,8,2,3,4]
#print(li.index(8))

# print(ord('z')-ord('a'))

#n= int(input()); s= input(); li1=[]; li2=[]; li3=[0]*26; cn=0; bl_falan=0
#for i in s:
#    if i>='A' and i<='Z':
#        li1.append(i)
#    else:
#        li2.append(i)
#        
#for i in range(n-1):
#    if li1[i].lower()==li2[i]:
#        bl_falan=1
#    else:
#        ab= li1[i].lower()
#        #li3.append(li2[i])
#        li3[ord(li2[i])-ord('a')]+=1
#        if li3[ord(ab)-ord('a')]==0: #ab not in li3:
#            cn+=1
#        else:
#            li3[ord(ab)-ord('a')]-=1
#            
#print(cn)


a,b = input().split(); a,b= int(a), int(b)

while a>0 and b>0:
    if a>= 2*b: a%= b+b
    elif b>= 2*a: b%= a+a
    else: break
    
print(a,b)








































        




    















'''
Abdul Hamid Shaodagor High School   Joni Kanti Pal  01306261062 Redwan Haque Ratul  01846509454
Hasne Hena Girls High School   Saiyeda Shahinur Parveen    01819858004 Habibur Rahman  01825374474
       ''' 














        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        