Maximizing GCD Modulo M

You are given a positive integer m and an array y of length n such that \(0 \le y_i < m\) for every \(i\). Your task is to construct an array x of length n (each element must lie in the __int128 range) satisfying the following conditions:

1. For every \(i\), \(x_i \bmod m = y_i\). That is, \(x_i = y_i + k_i \cdot m\) for some integer \(k_i\) (possibly negative).
2. If we define \(d = \gcd(|x_1|, |x_2|, \dots, |x_n|)\), then \(d \bmod m\) must be maximum possible (i.e. as large as possible, with the maximum value being \(m-1\)).

Note: The input has a new sample test case added so please check it carefully. Also, remember that negative values for \(x_i\) are allowed as long as \(x_i-y_i\) is divisible by m.

Hint: Write each \(x_i\) in the form \(x_i = y_i + k_i\,m\). In order to achieve a \(d\) with \(d \equiv m-1 \; (\bmod\; m)\), one idea is to force every \(x_i\) to be divisible by \(m-1\) while ensuring that the greatest common divisor of the quotients (when divided by \(m-1\)) is coprime with m. One way to do this is to choose for each \(i\): \[ k_i = \begin{cases} (-y_i) \bmod (m-1) & \text{if } (-y_i) \bmod (m-1) \neq 0, \\ m-1 & \text{if } (-y_i) \bmod (m-1)=0, \end{cases} \] with an extra adjustment for at least one index (for instance, the first index) to ensure that the greatest common divisor is exactly \(m-1\). Then set: \[ x_i = y_i + m\cdot k_i. \] This construction guarantees \(x_i \equiv y_i \; (\bmod\; m)\) and \(m-1\) divides every \(x_i\), so \(\gcd(|x_1|,\dots,|x_n|)\) is a multiple of \(m-1\) and, with a slight adjustment, can be arranged to have remainder \(m-1\; (\bmod\; m)\).

inputFormat

The first line contains two integers n and m.

The second line contains n integers \(y_1, y_2, \dots, y_n\) separated by spaces.

outputFormat

Output n integers \(x_1, x_2, \dots, x_n\) separated by spaces, which form the constructed array.

sample

3 10
0 1 2

180 81 72