Astronaut Natasha arrived on Mars. She knows that the Martians are very poor aliens. To ensure a better life for the Mars citizens, their emperor decided to take tax from every tourist who visited the planet. Natasha is the inhabitant of Earth, therefore she had to pay the tax to enter the territory of Mars.

There are $n$ banknote denominations on Mars: the value of $i$-th banknote is $a_i$. Natasha has an infinite number of banknotes of each denomination.

Martians have $k$ fingers on their hands, so they use a number system with base $k$. In addition, the Martians consider the digit $d$ (in the number system with base $k$) divine. Thus, if the last digit in Natasha's tax amount written in the number system with the base $k$ is $d$, the Martians will be happy. Unfortunately, Natasha does not know the Martians' divine digit yet.

Determine for which values $d$ Natasha can make the Martians happy.

Natasha can use only her banknotes. Martians don't give her change.


-----Input-----

The first line contains two integers $n$ and $k$ ($1 \le n \le 100\,000$, $2 \le k \le 100\,000$) — the number of denominations of banknotes and the base of the number system on Mars.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — denominations of banknotes on Mars.

All numbers are given in decimal notation.


-----Output-----

On the first line output the number of values $d$ for which Natasha can make the Martians happy.

In the second line, output all these values in increasing order.

Print all numbers in decimal notation.


-----Examples-----
Input
2 8
12 20

Output
2
0 4 
Input
3 10
10 20 30

Output
1
0 


-----Note-----

Consider the first test case. It uses the octal number system.

If you take one banknote with the value of $12$, you will get $14_8$ in octal system. The last digit is $4_8$.

If you take one banknote with the value of $12$ and one banknote with the value of $20$, the total value will be $32$. In the octal system, it is $40_8$. The last digit is $0_8$.

If you take two banknotes with the value of $20$, the total value will be $40$, this is $50_8$ in the octal system. The last digit is $0_8$.

No other digits other than $0_8$ and $4_8$ can be obtained. Digits $0_8$ and $4_8$ could also be obtained in other ways.

The second test case uses the decimal number system. The nominals of all banknotes end with zero, so Natasha can give the Martians only the amount whose decimal notation also ends with zero.

Difficulty: competition

Starter code:

Solutions:
import math
n,k=map(int,input().split())
g=k
for a in map(int,input().split()):
 g=math.gcd(g,a)
print(k//g)
print(' '.join(map(str,range(0,k,g))))

import math
n,k=map(int,input().split())
g=k
for a in map(int,input().split()):
 g=math.gcd(g,a)
print(k//g)
print(*range(0,k,g))

import math
i=lambda:map(int,input().split())
n,k=i()
g=k
for a in i():g=math.gcd(g,a)
print(k//g)
print(*range(0,k,g))

from math import gcd
n,k=map(int,input().split())
g=0
l=list(map(int,input().split()))
for e in l:
    g=gcd(g,gcd(e,k))
print(k//g)
for i in range(0,k,g): print(i,end=' ')

from math import gcd
from functools import reduce


def main():
    n, k = map(int, input().split())
    g = reduce(gcd, map(int, input().split()), k)
    print(k // g, ' '.join(map(str, range(0, k, g))), sep='\n')


def __starting_point():
    main()

__starting_point()

from math import gcd

N, K = map(int, input().split())
A = list(map(int, input().split()))

g = 0
for Ai in A: g = gcd(g, Ai)

s = set()
x = 0
while x not in s:
    s.add(x)
    x = (x + g) % K

print(len(s))
print(*sorted(s))

import math
i=lambda:map(int,input().split())
n,k=i()
g=k
for a in i():g=math.gcd(g,a)
print(k//g)
print(*range(0,k,g))

import math
from functools import reduce
a,b = map(int,input().split())
c = list(map(int,input().split()))
d = c[0]
for j in range(a):
    d = math.gcd(d,c[j])
    if d == 1:
        break
e = math.gcd(d,b)
print(b//e)
#f = [i for i in range(b) if i%e == 0]
#g = " ".join(str(k) for k in range(b) if k%e == 0)
print(" ".join(str(k) for k in range(b) if k%e == 0))

def gcd(a,b):
    return  a if 0==b else gcd(b,a%b)



n,k=map(int,input().split(" "))
#print(k)
den=list(map(int,input().split(" ")))
g=0
for i in den:
    g=gcd(g,i)

d=[]
dic={}
i=0
while (i<k):
    val=(i*g)%k
    #print("Value="+str(val))
    if(not val in dic):
        d.append(val)
        dic[val]=1
        i=i+1
    else:
        i=i+1
        continue
print(len(d))
d.sort()
for val in d:
    print(val,end=" ")


def nod(a,b):
    while a!=0 and b!=0:
        if a>b:
            a,b=b,a%b
        else:
            b,a=a,b%a
    return a+b
n ,k = map(int, input().split())  
a = [int(j) for j in input().split()] 
c = a[0]
for i in range(1,n):
    c = nod(c,a[i])
    if c==1:
        break
e = nod(c,k)
if c==1 or e==1:
    print(k)
    for i in range(k):
        print(i, end=" ")

if e>1:
    c = k//e
    print(c)
    for i in range(c):
        print(i*e, end=' ')
    
    
    


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

n, k = map(int, input().split(' '))
aa = list(map(int, input().split(' ')))

m = k
for a in aa:
    m = gcd(m, a)

print(k // m)
for i in range(0, k, m):
    print(i, end=' ')
print()


from functools import reduce
from math import gcd

_, k = map(int, input().split())
g = reduce(gcd, [k] + list(map(int, input().split())))
print(k // g)
print(" ".join(str(l) for l in range(0, k, g)))

from math import gcd
n,k=map(int,input().split())
it=list(map(int,input().split()))
it=[i%k for i in it]
it=[i for i in it if i!=0]

try:
    gc=it[0]
    for i in range(1,len(it)):
        gc=gcd(it[i],gc)
    gc=gcd(k,gc)
    print(k//gc)
    for i in range(k//gc):
        print(i*gc,end=" ")
except:
    print(1)
    print(0)


from math import gcd
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
g = 0
for i in a:
    g = gcd(g, i)
ans = set()
ans.add(g % k)
for i in range(k):
    ans.add((i * g) % k)
print(len(ans))
print(*sorted(list(ans)))



import math
def binpow(a, n):
	if n == 0:
		return 1
	if n % 2 == 1:
		return binpow(a, n - 1) * a
	else:
		b = binpow(a, n //2)
		return b * b
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
gcd = a[0]
for i in range(1, n):
	gcd = math.gcd(gcd, a[i])
s = set()
d = gcd % k
isk = gcd
while d not in s:
	s.add(d)
	gcd += isk
	d = gcd % k
print(len(s))
print(*sorted(s))



import math
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
ddc = 0
f = 1
ans = set()
for x in a:
	if f:
		ddc = x%k
	o = 0
	o = x%k
	if not f:
		ddc = math.gcd(ddc, o)
	
	if o == 1:
		print(k)
		print(*list(range(k)))
		return
	f = 0
	'''
	if k%2 != o%2 and math.gcd(k, o)==1:
		print(k)
		
		print(*range(k))
		return
	
	if not o in ans:
		yy = o
		ans.add(o)
		while o != 0:
			o+=yy
			o%=k
			ans.add(o)
		ans.add(0)
	
a = list(sorted(ans))
for i in range(len(a)):
	for j in range(i , len(a)):
		ans.add((a[i]+a[j])%k)
'''
yy = ddc
while yy:
	ans.add(yy)
	yy+=ddc
	yy%=k
ans.add(0)
print(len(ans))
print(*(sorted(ans)))



n,k=list(map(int,input().split()))
g=lambda x:int(x)%k
a=list(map(g,input().split()))
def nod(a,b):
    while b>0:
        a%=b
        a,b=b,a
    return a
c=k
for x in a:
    if x!=0:
        c=nod(c,x)
print(k//c)
print(' '.join(map(str,list(range(0,k,c)))))



def gcd(a, b):
	if (a < b):
		a, b = b, a
	if (b == 0):
		return a
	return gcd(b, a % b)


n, k = list(map(int, input().split()))
l = list(map(int, input().split()))
gcdd = k
for i in range(n):
	gcdd = gcd(gcdd, l[i])
if (gcdd == 0):
	print(1)
	print(0)
else:
	print(k // gcdd)
	ans = []
	for i in range(1, k // gcdd + 1):
		ans.append((i * gcdd) % k)
print(' '.join(map(str, sorted(ans))))




n, k = list(map(int, input().split()))
a = list(map(int, input().split()))

def gcd(a, b):
	if (b == 0):
		return a
	return gcd(b, a%b)

g = 0

for i in a:
	g = gcd(g, i)

res = set()
for i in range(0, k * g, g):
	res.add(i % k)

print(str(len(res)) + " \n" + " ".join(map(str, sorted(res))))


import sys
import math
from collections import defaultdict
n,k=list(map(int,sys.stdin.readline().split()))
a=list(map(int,sys.stdin.readline().split()))
l=[0 for _ in range(n)]
for i in range(n):
    l[i]=a[i]%k
ans=set()
ans.add(0)
vis=defaultdict(int)
x=0
for i in range(n):
    x=math.gcd(x,l[i])
    '''if l[i]!=0:
        if k%l[i]!=0 and vis[l[i]]==0:
            vis[l[i]]=1
            x=math.gcd(k,l[i])
            st=0
            while st*x<k:
                ans.add(st*x)
                st+=1
            if x==1:
                print(len(ans))
                res=list(ans)
                res.sort()
                print(*res)
                return
        else:
            if vis[l[i]]==0:
                st=0
                vis[l[i]]=1
                while st*l[i]<k:
                    ans.add(st*l[i])
                    st+=1'''
st=0
x=math.gcd(x,k)
while st*x<k and x!=0:
    ans.add(st*x)
    st+=1
print(len(ans))
res=list(ans)
res.sort()
print(*res)


import sys
import math
from collections import defaultdict
n,k=list(map(int,sys.stdin.readline().split()))
a=list(map(int,sys.stdin.readline().split()))
l=[0 for _ in range(n)]
for i in range(n):
    l[i]=a[i]%k
ans=set()
ans.add(0)
vis=defaultdict(int)
x=0
for i in range(n):
    x=math.gcd(x,l[i])
st=0
x=math.gcd(x,k)
while st*x<k and x!=0:
    ans.add(st*x)
    st+=1
print(len(ans))
res=list(ans)
res.sort()
print(*res)


def gcd(a,b):
    if b==0:
        return a
    if a%b==0:
        return b
    else:
        return gcd(b,a%b)
    
    
n,k=list(map(int,input().split()))
a=list(map(int,input().split()))
for i in range(n):
    a[i]=a[i]%k
a.append(k)
b=0
for i in range(n+1):
    b=gcd(b,a[i])
c=[]
for i in range(0,k,b):
    c.append(i)

print(len(c))
print(*c)