Problem 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 case has been added to this problem, please check it carefully.

Xiao Y has given you an array \( y \) of length \( n \) and a positive integer \( m \), ensuring that \( 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 \mod m = y_i \);
3. \( \gcd(|x_1|, \cdots, |x_n|) \mod m \) is maximized.

Note that \( x_i \) can be negative, in which case \( m \mid (x_i - y_i) \) and \( 0 \le y_i < m \).

Input Format

The first line contains two positive integers \( n \) and \( m \).

The next line contains \( n \) non-negative integers representing the values of \( x_i \mod m \).

Output Format

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

The next line contains \( n \) integers representing \( x_i \).

Sample Input and Output

Sample Input #1

1 10
4

Sample Output #1

6
-6

Sample Input #2

1 10
7

Sample Output #2

7
7

Sample Input #3

2 9
3 3

Sample Output #3

6
12 -6

Sample Input #4

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

Sample Output #4

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

Notes

Data Range

This problem uses subtask testing.

Subtask 1 ($30$ pts): \( m \) is a prime number.

Subtask 2 ($70$ pts): No additional constraints.

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 case:

If your output format is incorrect, you will receive $0$ points.

If any number in your output is out of the __int128 range, it may cause overflow, and you may not get the expected score.

If your array \( x \) does not match the given \( y \), you will receive $0$ points.

If your array \( x \) does not match the \( g \) you output, you will receive $0$ points.

If your \( g \) is not the maximum, you will receive $0$ points.

Otherwise, you will receive all points for that test case.

见题面 Input 部分

见题面 Output 部分