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 ai
. 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≤n≤100000, 2≤k≤100000
) — the number of denominations of banknotes and the base of the number system on Mars.
The second line contains n
integers a1,a2,…,an (1≤ai≤109
) — 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
Copy
2 812 20
Output
Copy
20 4
Input
Copy
3 1010 20 30
Output
Copy
10
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 148 in octal system. The last digit is 48
.
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 408. The last digit is 08
.
If you take two banknotes with the value of 20
, the total value will be 40, this is 508 in the octal system. The last digit is 08
.
No other digits other than 08
and 48 can be obtained. Digits 08 and 48
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.
#includeusing namespace std;typedef long long ll;#define rep(i,a,b) for(int i=a;i=a;i--)set st;ll gcd(ll a,ll b){ return b==0?a:gcd(b,a%b);}/*相似题:蓝桥杯,包子凑数核心思想:a1*x1+a2*x2+...+an*xn==gcd(a1,a2,...,an)*? <---原理:拓展欧几里得也就是他们能凑出来的树肯定是,gcd的倍数,然后在mod系下的话,只要枚举到mod就好了当时只想着把他们都转化成mod系下的数字,然后在进行计算,事实就是这样会更麻烦*/int main(){ int n,m; scanf("%d %d",&n,&m); ll val,G; rep(i,1,n+1){ scanf("%lld",&val); if(i==1)G=val; else G=gcd(G,val); } for(ll i=0,j=0;j<=m;j++,i+=G){ st.insert(i%m); } printf("%d\n",st.size()); set::iterator it; for(it=st.begin();it!=st.end();it++){ printf("%lld%c",*it,it==st.end()?"\n":" "); } return 0;}
12月16日,国家能源局发布1-11月份全国电力工业统计数据。截至11月底,全国累计发电装机容量约251亿千瓦,同比增长81%。其中,风电装机容更多
2022-12-20 08:59:521-11月,全社会用电量同比增长,城乡居民生活用电量保持两位数增长;发电装机延续绿色发展趋势,发电量增速有所放缓;除太阳能发电外,其更多
2022-12-20 09:04:12记者从国家发展改革委了解到,目前,全国能源供需总体平稳有序,人民群众温暖过冬能够得到有效保障。 从煤炭生产看,1—11月份,全国原更多
2022-12-20 09:01:19近日,受寒潮天气影响,我国大部分地区出现剧烈降温,能源保供进入迎峰度冬关键期。能源大省山西深挖增产潜力,煤炭产量、电力外送规模、更多
2022-12-20 08:59:1512月18日下午,煤炭钢铁行业交流机制工作会在广东省珠海市召开,中国煤炭工业协会、中国钢铁工业协会、中国煤炭运销协会,山西焦煤、山东更多
2022-12-19 14:02:1412月17日,中国焦煤品牌集群高层领导座谈会在广东省珠海市召开。龙煤集团党委书记、董事长王佳喜,淮北矿业集团党委书记、董事长方良才,更多
2022-12-19 14:08:28盘江股份董事长朱家道12月15日在业绩交流会上表示,公司尚未释放煤炭产能约500万吨,将通过改善生产条件等方式方法,尽快释放产能,提升原更多
2022-12-19 10:08:24内蒙古自治区统计局消息,1-11月份,全区规模以上工业企业原煤产量107亿吨,同比增长121%,保持了今年以来两位数增长的态势。从当月情况看更多
2022-12-19 09:54:45今年以来,福建八方港口积极调整经营思路,多举措拓展内贸煤市场。截至11月30日,港口完成内贸卸船量3047万吨,同比上涨1112%,比去年全年更多
2022-12-19 10:12:07为了最大限度地减少疫情对经济社会发展影响,近日,吕梁市出台支持工业企业加快复工复产达产达效15条措施,促进全市经济快速回升向好。 更多
2022-12-19 10:04:25