CF1045B.Space Isaac

Everybody seems to think that the Martians are green, but it turns out they are metallic pink and fat. Ajs has two bags of distinct nonnegative integers. The bags are disjoint, and the union of the sets of numbers in the bags is ${0,1,…,M-1}$, for some positive integer $M$. Ajs draws a number from the first bag and a number from the second bag, and then sums them modulo $M$.

What are the residues modulo $M$ that Ajs cannot obtain with this action?

所有人都以为火星人是绿色的，但事实证明他们是金属粉红色且胖乎乎的。Ajs 有两个装有互异非负整数的袋子。这两个袋子互不相交，且两个袋子中所有数字构成的集合的并集为 $\{0,1,\dots,M-1\}$，其中 $M$ 是某个正整数。Ajs 从第一个袋子中随机抽取一个数，再从第二个袋子中随机抽取一个数，然后将这两个数对 $M$ 取模求和。

通过这一操作，Ajs 无法得到哪些模 $M$ 的剩余类？

The first line contains two positive integer $N$ ($1 \leq N \leq 200\,000$) and $M$ ($N+1 \leq M \leq 10^{9}$), denoting the number of the elements in the first bag and the modulus, respectively.

The second line contains $N$ nonnegative integers $a_1,a_2,\ldots,a_N$ ($0 \leq a_1 \lt a_2 \lt \ldots \lt a_N \lt M$), the contents of the first bag.

第一行包含两个正整数 $N$（$1 \leq N \leq 200\,000$）和 $M$（$N+1 \leq M \leq 10^{9}$），分别表示第一个袋子中元素的个数以及模数。

第二行包含 $N$ 个非负整数 $a_1,a_2,\ldots,a_N$（$0 \leq a_1 \lt a_2 \lt \ldots \lt a_N \lt M$），表示第一个袋子中的内容。

In the first line, output the cardinality $K$ of the set of residues modulo $M$ which Ajs cannot obtain.

In the second line of the output, print $K$ space-separated integers greater or equal than zero and less than $M$, which represent the residues Ajs cannot obtain. The outputs should be sorted in increasing order of magnitude. If $K$=0, do not output the second line.

第一行输出 Ajs 无法得到的模 $M$ 同余类集合的基数 $K$。

输出的第二行包含 $K$ 个用空格分隔的整数，每个整数均大于等于 $0$ 且小于 $M$，表示 Ajs 无法得到的同余类。这些整数应按数值升序排列。若 $K=0$，则不输出第二行。

In the first sample, the first bag and the second bag contain ${3,4}$ and ${0,1,2}$, respectively. Ajs can obtain every residue modulo $5$ except the residue $2$: $ 4+1 \equiv 0, , 4+2 \equiv 1, , 3+0 \equiv 3, , 3+1 \equiv 4 $ modulo $5$. One can check that there is no choice of elements from the first and the second bag which sum to $2$ modulo $5$.

In the second sample, the contents of the first bag are ${5,25,125,625}$, while the second bag contains all other nonnegative integers with at most $9$ decimal digits. Every residue modulo $1\,000\,000\,000$ can be obtained as a sum of an element in the first bag and an element in the second bag.

在第一个样例中，第一个袋子和第二个袋子分别包含 $\{3,4\}$ 和 $\{0,1,2\}$。Ajs 可以得到模 $5$ 的所有剩余类，除了剩余类 $2$：$ 4+1 \equiv 0,, 4+2 \equiv 1,, 3+0 \equiv 3,, 3+1 \equiv 4 \pmod{5}$。可以验证，不存在从第一个袋子和第二个袋子中各选一个元素，使其和模 $5$ 等于 $2$。

在第二个样例中，第一个袋子的内容为 $\{5,25,125,625\}$，而第二个袋子包含所有其余的、至多有 $9$ 位十进制数字的非负整数。模 $1\,000\,000\,000$ 的每一个剩余类均可表示为第一个袋子中某个元素与第二个袋子中某个元素之和。