Все думают, что марсиане зеленые, но на самом деле они розоватые с металлическим отливом и полные. У Ажса есть два мешочка с различными неотрицательными числами. Числа в мешочках не пересекаются, а объединение множеств чисел равно $$$\{0,1,…,M-1\}$$$ для некоторого положительного числа $$$M$$$.
Ажс достает одно число из первого мешочка, одно число из второго, и вычисляет их сумму по модулю $$$M$$$.
Какие остатки по модулю $$$M$$$ Ажс не может получить после такого действия?
Первая строка содержит два положительных числа $$$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<a_2< \ldots< a_N<M$$$) — содержимое первого мешочка.
В первой строке выведите мощность $$$K$$$ множества остатков по модулю $$$M$$$, которые Ажс не может получить.
На второй строке выведите $$$K$$$ целых чисел, больших или равных нуля и меньших $$$M$$$ — остатки, которые Ажс не может получить. Эти числа должны быть упорядочены по возрастанию. Если $$$K$$$=0, не выводите вторую строку.
2 5
3 4
1
2
4 1000000000
5 25 125 625
0
2 4
1 3
2
0 2
В первом примере первый и второй мешочки содержат числа $$$\{3,4\}$$$ и $$$\{0,1,2\}$$$ соответственно. Ажс может получить любой остаток по модулю $$$5$$$, кроме $$$2$$$: $$$ 4+1 \equiv 0, \, 4+2 \equiv 1, \, 3+0 \equiv 3, \, 3+1 \equiv 4 $$$ по модулю $$$5$$$. Вы можете убедиться, что невозможно выбрать число из первого списка и число из второго списка так, что их сумма равняется $$$2$$$ по модулю $$$5$$$.
Во втором примере содержимое первого мешочка равно $$$\{5,25,125,625\}$$$, в то время как второй мешочек содержит все остальные целые неотрицательные числа, имеющие не более $$$9$$$ цифр в десятичной записи. Все остатки по модулю $$$1\,000\,000\,000$$$ могут быть получены как сумма элемента из первого мешочка и элемента из второго мешочка.
Название |
---|