tripping-on-nothingness

Little Pandey is someone who is lazy, and when he's around his best friend GJ, he becomes super lazy. Pandey thinks that he is a Math-wizard, so he picks up a number S and asks GJ to throw him a challenge around that number.  

GJ explains Little Pandey a property called nothingness and decides to ask him Q queries based on it.
In mathematical terms, Nothingness(A, B) is defined as the maximum M that (A%M==0 and B%M==0). (You can read about the Modulus Operator here.)
In the i-th query GJ says a number Ai and Little Pandey must find Nothingness(S, Ai).

But, Pandey is the laziest of all.
He won't give the same answer twice or more times.
When he calculates a new answer and it turns out that he has said it before, now he will say -1 instead.

Help Little Pandey solve the Q queries.

Input format:

The first line contains two integers S and Q, denoting the number chosen by Pandey and the number of queries, respectively. The i-th of the next Q lines contains a single integer Ai.

Output format:

For every query, output Pandey's answer in a separate line.

Constraints:
1 ≤ S ≤ 10^5
1 ≤ Q ≤ 10^5
1 ≤ Ai ≤ 10^9

SAMPLE INPUT
10 5
6
5
8
100
5

SAMPLE OUTPUT
2
5
-1
10
-1

Difficulty: MEDIUM_HARD
Tags: Fundamentals

Mathematics

Starter code:

Solutions:
from fractions import gcd
num, tc  = list(map(int, input().split(" ")))
done = set()
while tc > 0:
	tc -= 1
	q = int(input())
	res = gcd(num, q)
	if res in done:
		print(-1)
	else:
		done.add(res)
		print(res)


from fractions import gcd 
s, q = list(map(int, input().split()))
allgcd = []
for i in range(q):
	t = eval(input())
	ans = gcd(s, t)
	if ans in allgcd:
		print("-1")
	else:
		print(ans)
		allgcd.append(ans)
	


from fractions import gcd
s,q = list(map(int,input().split()))
dic = {}
for i in range(q):
	n = eval(input())
	ans = gcd(s,n)
	if ans in dic:
		print(-1)
	else:
		print(ans)
		dic[ans] = 1


from fractions import gcd
a,b=list(map(int,input().split()))
d=[]
for x in range(b):
	c=gcd(a,eval(input()))
	if c not in d:
		d.append(c)
		print(c)
	else :
		print("-1")
	


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
def gcd(u, v):
	while v:
		u, v = v, u % v
	return abs(u)
		
s,cases = list(map(int,input().split()))
temp = set()
while(cases != 0):
	cases = cases - 1
	a = int(input())
	t = gcd(s,a)
	if t in temp:
		print((-1))
	else:
		temp.add(t)
		print(t)
	


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
def gcd(u, v):
	while v:
		u, v = v, u % v
	return abs(u)
		
s,cases = list(map(int,input().split()))
temp = set()
while(cases != 0):
	cases = cases - 1
	a = int(input())
	t = gcd(s,a)
	if t in temp:
		print((-1))
	else:
		temp.add(t)
		print(t)
	


def gcd(a,b):
	rem=1
	div=a
	divd=b
	while rem!=0:   
		rem=divd%div
		if rem==0:
			return div
		else:
			divd=div
			div=rem
		

a,query=list(map(int,input().split()))
l=[]
for i in range(query):
	b=int(input())
	nothing=gcd(a,b)
	if nothing in l:
		print(-1)
	else:
		l.append(nothing)
		print(nothing)
	


from fractions import gcd
s,q=list(map(int,input().split()))
dic={}
for i in range(q):
	n=int(input())
	ans=gcd(s,n)
	if ans in dic:
		print('-1')
	else:
		print(ans)
		dic[ans]=1
		


from fractions import gcd

d, q=list(map(int, input().split()))
s=[]
for i in range(q):
	a=eval(input())
	ans=gcd(d, a)
	if ans in s:
		print(-1)
	else:
		print(ans)
		s.append(ans)




def gcd(a,b):
	if b==0:
    		return a
    	else:
    		return gcd(b,a%b)
s,t = tuple(map(int,input().split()))
val = 0
a = [0]*(s+1)
for i in range(t):
	p = int(eval(input()))
	val = gcd(s,p)
	if(a[val] == 0):
		a[val] = 1
		print(val)
	else:
		print((-1))




from fractions import gcd

d, q=list(map(int, input().split()))
s=[]
for i in range(q):
	a=eval(input())
	ans=gcd(d, a)
	if ans in s:
		print(-1)
	else:
		print(ans)
		s.append(ans)




def gcd(a,b):
	A=b
	B=a%b
	if B==0:
		return A
	else:
		return gcd(A,B)
s,q=list(map(int,input().split()))		
li=[]
while q:
	q-=1
	a=int(input())
	A=gcd(s,a)
	if A not in li:
		print(A)
	else:
		print(-1)
	li.append(A)
	#print li


def gcd(a, b):
   
	while b:
		a, b = b, a%b
	return a
a,b=list(map(int,input().split()))
h=[]
while b:
	z=eval(input())
	x=gcd(a,z)
	if x in h:
		print("-1")
	else:
		print(x)
		h.append(x)
	b=b-1
	
		
		



from fractions import gcd
s,q=list(map(int,input().split()))
d={}
while q:
	q-=1
	x=eval(input())
	m=gcd(s,x)
	
	if m  not in d:
		d[m]=-1
		print(m)
		#d[m]=-1
	else:
		print('-1')


from fractions import gcd
d = 100001 * [0]
s, q = list(map(int, input().split()))
for _ in range(q):
	x = gcd( s, int(input()))
	if d[x]:
		print(-1)
	else:
		d[x] = 1
		print(x)


s,q = input().split(" ")
s = int(s)
q = int(q)

saved_ans = []

def gcd(a, b):
	while a!=0:
		c = a
		a = b%a
		b = c
	return b;

for i in range(q):
	a = input()
	a = int(a)
	ans = gcd(s, a)
	
	if ans in saved_ans:
		print("-1")
	else:
		print(ans)
		
	saved_ans.append(ans)


from fractions import gcd
clis=[]
S,Q=list(map(int,input().strip().split()))
for i in range (Q):
	k=gcd(S,eval(input()))
	if k in clis:
		print(-1)
	else:
		print(k)
		clis.append(k)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
import fractions

text=input().split()
S=int(text[0])
Q=int(text[1])
s=set()
for i in range(Q):
    
	A=int(input())
	ans=fractions.gcd(S,A)
	
	if ans in s:
		print('-1')
	else:
		s.add(int(ans))
		print(ans)


def gcdIter(a,b):
	'''
	a, b: positive integers
	
	returns: a positive integer, the greatest common divisor of a & b.
	'''
	# Your code here
	test=min(a,b)
	while test>=1:
		if a%test==0 and b%test==0:
			return test
		test-=1
	   

import fractions

S,tc=list(map(int,input().split(' ')))
#print S,tc
already_occured=[]
while tc:
	tc=tc-1
	A=int(input())
	#gcd=gcdIter(A,S)
	gcd=fractions.gcd(A,S)
	if gcd in already_occured:
		print(-1)
	else:
		already_occured.append(gcd)
		print(gcd)