← 返回题目列表

Codeforces · 1010/C

C. 边框

中文机器翻译题面 查看原题

宇航员娜塔莎抵达火星。她知道火星人是非常可怜的外星人。为了确保火星公民过上更好的生活,他们的皇帝决定向每一位访问该星球的游客征税。娜塔莎是地球上的居民,因此她必须缴纳税款才能进入火星领土。

火星上有 $$$n$$$ 纸币面额:第 $$$i$$$ 纸币的面值为 $$$a_i$$$。娜塔莎拥有无限数量的每种面额的钞票。

火星人的手上有 $$$k$$$ 手指,因此他们使用以 $$$k$$$ 为基数的数字系统。此外,火星人认为数字$$$d$$$(在以$$$k$$$为基数的数字系统中)是神圣的。因此,如果娜塔莎的税额以 $$$k$$$ 为基数的数字系统中的最后一位数字是 $$$d$$$,火星人就会很高兴。不幸的是,娜塔莎还不知道火星人的神数。

确定哪些值 $$$d$$$ Natasha 可以让火星人感到高兴。

娜塔莎只能使用她的钞票。火星人不给她零钱。

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 100\,000$$$, $$$2 \le k \le 100\,000$$$)——纸币的面额数量和火星上的数字系统的基数。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 火星上纸币的面额。

所有数字均以十进制表示。

输出

在第一行输出 Natasha 可以让火星人高兴的值 $$$d$$$ 的数量。

在第二行中,按升序输出所有这些值。

以十进制形式打印所有数字。

示例

输入 #1

2 8
12 20

输出 #1

2
0 4

输入 #2

3 10
10 20 30

输出 #2

1
0

注意

考虑第一个测试用例。它使用八进制数字系统。

如果您取出一张面值 $$$12$$$ 的钞票,您将得到八进制的 $$$14_8$$$。最后一位数字是$$$4_8$$$。

如果您取出一张价值 $$$12$$$ 的钞票和一张价值 $$$20$$$ 的钞票,则总价值将为 $$$32$$$。在八进制系统中,它是$$$40_8$$$。最后一位数字是$$$0_8$$$。

如果您拿两张面值为$$$20$$$的钞票,总价值将为$$$40$$$,八进制中为$$$50_8$$$。最后一位数字是$$$0_8$$$。

除了$$$0_8$$$ 和$$$4_8$$$ 之外,无法获取其他数字。数字$$$0_8$$$和$$$4_8$$$也可以通过其他方式获得。

第二个测试用例使用十进制数字系统。所有纸币的面值都以零结尾,所以娜塔莎只能给火星人十进制也以零结尾的金额。