「WHOI-4」ggcd
题目背景
如何输入输出 `__int128`：
```cpp
__int128 read() {
char c = getchar();
__int128 x = 0;
bool f = 0;
for (; !isdigit(c); c = getchar()) f ^= !(c ^ 45);
for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
if (f) x = -x;
return x;
}
void write(__int128 x, char c = '\0') {
if (x < 0) putchar('-'), x = -x;
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
if (c != '\0') putchar(c);
}
```
题目描述
**本题已新增一组样例，请注意查看。**
小 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$。
输入输出格式
输入格式
第一行两个正整数 $n,m$。
接下来一行 $n$ 个非负整数，代表 $x_i \bmod m$ 的值。
输出格式
第一行一个非负整数 $g$，代表 $\gcd(|x_1|,|x_2|,\cdots,|x_n|)\mod m$ 的可能最大值。
接下来一行 $n$ 个整数，代表 $x_i$。
输入输出样例
输入样例 #1
1 10
4输出样例 #1
6
-6输入样例 #2
1 10
7输出样例 #2
7
7输入样例 #3
2 9
3 3输出样例 #3
6
12 -6输入样例 #4
10 7
1 2 3 4 5 6 0 1 2 3输出样例 #4
6
36 30 24 18 12 6 42 -6 30 24说明
**数据范围**
**本题采用捆绑测试。**
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$ 分。
否则你将获得该测试点的所有分数。