Vulnerable Kerbals

题意翻译

### 题目描述 给出两个整数 $n, m$,在给出一个大小为 $n$ 的集合 $B$,且 $\forall y \in B$ 有 $0 \leq y < m$。现要求构造一个序列 $A$,满足以下条件: - $\forall x \in A$ 有 $0 \leq x < m$。 - $\forall i, j, 1 \leq i, j \leq |A|$, 有 $\prod \limits _{k = 1}^{i}A_k \not\equiv \prod \limits _{k = 1}^{j}A_k \pmod m$ - $\forall i, y, 1 \leq i \leq |A|, y \in B$, 有 $\prod \limits _{k = 1}^{i}A_k \not\equiv y \pmod m$ 在序列 $A$ 合法的条件下满足长度最大化,并给出一种构造方案。 ### 输入格式 第一行两个整数 $n, m$。 第二行(若 $n = 0$ 则没有)输入 $n$ 个整数,表示集合 $B$。 ### 输出格式 第一行一个整数,表示序列 $A$ 的最大长度 $|A|$。 第二行 $|A|$ 个整数,表示序列 $A$。 ### 数据范围 $0 \leq n, m \leq 2 \times 10^5$。

题目描述

You are given an integer $ m $ , and a list of $ n $ distinct integers between $ 0 $ and $ m-1 $ . You would like to construct a sequence satisfying the properties: - Each element is an integer between $ 0 $ and $ m-1 $ , inclusive. - All prefix products of the sequence modulo $ m $ are distinct. - No prefix product modulo $ m $ appears as an element of the input list. - The length of the sequence is maximized. Construct any sequence satisfying the properties above.

输入输出格式

输入格式


The first line of input contains two integers $ n $ and $ m $ ( $ 0<=n&lt;m<=200000 $ ) — the number of forbidden prefix products and the modulus. If $ n $ is non-zero, the next line of input contains $ n $ distinct integers between $ 0 $ and $ m-1 $ , the forbidden prefix products. If $ n $ is zero, this line doesn't exist.

输出格式


On the first line, print the number $ k $ , denoting the length of your sequence. On the second line, print $ k $ space separated integers, denoting your sequence.

输入输出样例

输入样例 #1

0 5

输出样例 #1

5
1 2 4 3 0

输入样例 #2

3 10
2 9 1

输出样例 #2

6
3 9 2 9 8 0

说明

For the first case, the prefix products of this sequence modulo $ m $ are $ [1,2,3,4,0] $ . For the second case, the prefix products of this sequence modulo $ m $ are $ [3,7,4,6,8,0] $ .