Generate an N-length sequence from two given arrays whose GCD is K

  

  
  
def GCD(a, b):
    if not b:
        return a
    return GCD(b, a % b)
  

def GCDArr(a):
    ans = a[0]
    for i in a:
        ans = GCD(ans, i)
    return ans
  

def findSubseqUtil(a, b, ans, k, i):
  
    
    
    if len(ans) == len(a):
  
        
        
        if GCDArr(ans) == k:
            print(ans)
            return True
  
        else:
            return False
  
    
    
    if not a[i] % K:
        ans.append(a[i])
  
        
        temp = findSubseqUtil(a, b, ans, k, i+1)
  
        
        
        if temp == True:
            return True
  
        
        
        ans.pop()
  
    
    
    if not b[i] % k:
  
        ans.append(b[i])
  
        
        temp = findSubseqUtil(a, b, ans, k, i+1)
  
        
        
        if temp == True:
            return True
  
        
        
        ans.pop()
  
    return False
  

def findSubseq(A, B, K, i):
  
    
    ans = []
  
    findSubseqUtil(A, B, ans, K, i)
  
    
    
    if not ans:
        print(-1)
  

  
  

A = [5, 3, 6, 2, 9]
B = [21, 7, 14, 12, 28]
  

K = 3
  

ans = findSubseq(A, B, K, 0)