Description

本题已新增一组样例，请注意查看。

小 Y 给了你长度为 $n$ 的数组 $y$ 以及一个正整数 $m$，保证 $0\le y_i<m$，请你构造一个同样长为 $n$ 的数组 $x$，使得：

1. $x_i$ 在 __int128 范围内；
2. $x_i\bmod m=y_i$；
3. $\gcd(|x_1|,\cdots,|x_n|)\bmod m$ 最大。

注意，$x_i$ 可以为负，此时 $m\mid (x_i-y_i)$ 且 $0\le y_i<m$。

Input Format

第一行两个正整数 $n,m$。

接下来一行 $n$ 个非负整数，代表 $x_i \bmod m$ 的值。

Output Format

第一行一个非负整数 $g$，代表 $\gcd(|x_1|,|x_2|,\cdots,|x_n|)\mod m$ 的可能最大值。

接下来一行 $n$ 个整数，代表 $x_i$。

1 10
4

6
-6

1 10
7

7
7

2 9
3 3

6
12 -6

10 7
1 2 3 4 5 6 0 1 2 3

6
36 30 24 18 12 6 42 -6 30 24

Hint

数据范围

本题采用捆绑测试。

Subtask 1（$30$ pts）：$m$ 是素数。

Subtask 2（$70$ pts）：无特殊限制。

对于所有数据，保证 $2\le m \le10^9$，$1\le n\le10^6$。

关于 Special Judge

对于每个测试点：

如果你输出的格式不正确，你将会获得 $0$ 分。

如果你输出的数中有不在 __int128 范围的数，可能导致溢出所以你可能无法获得预期的分数。

如果你的数列 $x$ 不符合题目给定的 $y$，你将会获得 $0$ 分。

如果你的数列 $x$ 不符合你输出的 $g$，你将会获得 $0$ 分。

如果你的 $g$ 不为最大，你将会获得 $0$ 分。

否则你将获得该测试点的所有分数。