← 返回题目列表

Codeforces · 1510/D

D. 数字

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

戴安娜喜欢玩数字。她有 $$$n$$$ 卡片,上面写着正整数 $$$a_i$$$。她利用空闲时间计算卡片上的数字。她选择卡片的一个非空子集,并将上面写的所有数字 $$$a_i$$$ 相乘。

当数字的乘积以她最喜欢的数字 $$$d$$$ 结尾时,戴安娜很高兴。现在她很好奇应该选择什么卡片,以便卡片上的数字的乘积尽可能最大,并且乘积的最后一位小数位是 $$$d$$$。请帮助她。

输入

第一行包含整数 $$$n$$$ 和 $$$d$$$ ($$$1\le n\le 10^5$$$, $$$0\le d\le 9$$$)。第二行包含 $$$n$$$ 整数 $$$a_i$$$ ($$$1\le a_i\le 1000$$$)。

输出

在第一行,打印所选卡片的数量 $$$k$$$ ($$$1\le k\le n$$$)。在下一行,以任意顺序打印写在所选卡片上的数字。

如果无法选择产品以 $$$d$$$ 结尾的卡片子集,请打印单行 $$$-1$$$。

示例

输入
复制

6 4
4 11 8 2 1 13

输出
复制

5
1 2 4 11 13 

输入
复制

3 1
2 4 6

输出
复制

-1

输入
复制

5 7
1 3 1 5 3

输出
复制

-1

输入
复制

6 3
8 9 4 17 11 5

输出
复制

3
9 11 17 

输入
复制

5 6
2 2 2 2 2

输出
复制

4
2 2 2 2 

注意

在第一个示例中,$$$1 \times 2 \times 4 \times 11 \times 13 = 1144$$$,这是以数字 4 结尾的最大乘积。没有数字 1 的同一组卡片也是有效答案,以及带有或不带有 1 的 8、11 和 13 组也具有 1144 的乘积。

在第二个示例中,卡片上的所有数字都是偶数,并且它们的乘积不能以奇数 1 结尾。

在第三个示例中,唯一可能的乘积是 1、3、5、9、15 和 45,其中没有一个以数字 7 结尾。

在第四个示例中,$$$9 \times 11 \times 17 = 1683$$$,以数字 3 结尾。

在第五个示例中,$$$2 \times 2 \times 2 \times 2 = 16$$$,以数字 6 结尾。