P8961 "WHOI-4" ggcd

How to input and output `__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

**A new sample has been added to this problem. Please check it.** Little Y gives you an array $y$ of length $n$ and a positive integer $m$, guaranteeing $0 \le y_i < m$. Please construct an array $x$ of the same length $n$ such that: 1. $x_i$ is within the range of `__int128`. 2. $x_i \bmod m = y_i$. 3. $\gcd(|x_1|, \cdots, |x_n|) \bmod m$ is as large as possible. Note that $x_i$ **can be negative**. In this case, $m \mid (x_i - y_i)$ and $0 \le y_i < m$.

The first line contains two positive integers $n, m$. The next line contains $n$ non-negative integers, representing the values of $x_i \bmod m$.

The first line contains a non-negative integer $g$, representing the maximum possible value of $\gcd(|x_1|, |x_2|, \cdots, |x_n|) \bmod m$. The next line contains $n$ integers, representing $x_i$.

**Constraints** **This problem uses bundled testdata.** Subtask 1 ($30$ pts): $m$ is prime. Subtask 2 ($70$ pts): No special restrictions. For all data, it is guaranteed that $2 \le m \le 10^9$ and $1 \le n \le 10^6$. **About Special Judge** For each test point: If your output format is incorrect, you will get $0$ points. If any number you output is not within the range of `__int128`, it may cause overflow, so you may not get the expected score. If your sequence $x$ does not match the given $y$ in the statement, you will get $0$ points. If your sequence $x$ does not match the $g$ you output, you will get $0$ points. If your $g$ is not the maximum, you will get $0$ points. Otherwise, you will get full points for that test point. Translated by ChatGPT 5