给定一个整数 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]。