Background

How to input and output __int128:

__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);
}

Problem Description

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$.

Input Format

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$.

Output Format

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$.

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

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