← 返回题目列表

Codeforces · 772/C

C. 脆弱的坎巴拉人

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

给定一个整数 m 和一个由 0 到 m - 1 之间的 n 个不同整数组成的列表。

您想要构造一个满足以下属性的序列:

- 每个元素都是 0 到 m - 1 之间的整数(包括 0 和 m - 1)。
- 序列模 m 的所有前缀积都是不同的。
- 没有模 m 的前缀积作为输入列表的元素出现。
- 序列的长度最大化。

构造满足上述属性的任何序列。

输入

输入的第一行包含两个整数 n 和 m (0 ≤ n < m ≤ 200 000) — 禁止前缀乘积的数量和模数。

如果 n 非零,则下一行输入包含 0 到 m - 1 之间的 n 个不同整数,即禁止的前缀乘积。如果 n 为零,则该行不存在。

输出

在第一行,打印数字 k,表示序列的长度。

在第二行,打印 k 个空格分隔的整数,表示您的序列。

示例

输入 #1

0 5

输出 #1

5
1 2 4 3 0

输入 #2

3 10
2 9 1

输出 #2

6
3 9 2 9 8 0

注意

对于第一种情况,该序列模 m 的前缀积是 [1, 2, 3, 4, 0]。

对于第二种情况,该序列模m的前缀积是[3,7,4,6​​,8,0]。