E2. Астеризм (сложная версия)
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Различие между версиями заключается в ограничениях на $$$n$$$ и $$$a_i$$$. Вы можете делать взломы, только если обе версии этой задачи сданы.

Сначала Aoi придумал следующую идею для задачи по программированию:

Yuzu девочка, которая коллекционирует конфеты. Изначально, у нее есть $$$x$$$ конфет. Также есть $$$n$$$ врагов, пронумерованных целыми числами от $$$1$$$ до $$$n$$$. Враг $$$i$$$ имеет $$$a_i$$$ конфет.

Yuzu хочет получить перестановку $$$P$$$. Перестановкой называется массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$, расположенных в некотором порядке. Например, $$$\{2,3,1,5,4\}$$$ это перестановка, а $$$\{1,2,2\}$$$ это не перестановка (число $$$2$$$ встречается в массиве дважды) и $$$\{1,3,4\}$$$ тоже не является перестановкой (потому что $$$n=3$$$, но в массиве есть число $$$4$$$).

После этого, она проведет $$$n$$$ дуэлей с врагами по следующим правилам:

  • Если Yuzu сейчас имеет не меньше конфет, чем враг $$$P_i$$$, она побеждает в дуэли и получает $$$1$$$ конфету. Иначе, она проигрывает дуэль и ничего не получает.
  • Конфета, которую получает Yuzu в случае победы, будет использоваться в следующих дуэлях.

Yuzu хочет победить во всех дуэлях. Сколько существует возможных перестановок $$$P$$$, для которых это произойдет?

Эта задача была простой и неинтересной для Akari, друга Aoi. И Akari придумал следующую задачу, на основе описанной идеи:

Давайте определим $$$f(x)$$$ как количество возможных перестановок для целого числа $$$x$$$.

Вам дано число $$$n$$$, массив $$$a$$$ и простое число $$$p \le n$$$. Назовем целое положительное число $$$x$$$ хорошим, если значение $$$f(x)$$$ не делится на $$$p$$$. Найдите все хорошие числа $$$x$$$.

Решите задачу, предложенную Akari.

Входные данные

В первой строке находится два целых числа $$$n$$$, $$$p$$$ $$$(2 \le p \le n \le 10^5)$$$. Гарантируется, что число $$$p$$$ является простым (оно имеет ровно два делителя $$$1$$$ и $$$p$$$).

Во второй строке находится $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \le a_i \le 10^9)$$$.

Выходные данные

В первой строке выведите количество хороших чисел $$$x$$$.

Во второй строке выведите все хорошие числа $$$x$$$ в возрастающем порядке.

Гарантируется, что количество хороших чисел $$$x$$$ не превосходит $$$10^5$$$.

Примеры
Входные данные
3 2
3 4 5
Выходные данные
1
3
Входные данные
4 3
2 3 5 6
Выходные данные
2
3 4
Входные данные
4 3
9 1 1 1
Выходные данные
0
Входные данные
3 2
1000000000 1 999999999
Выходные данные
1
999999998
Примечание

В первом тесте $$$p=2$$$.

  • Если $$$x \le 2$$$ тогда нет ни одной перестановки, подходящей для Yuzu. Поэтому $$$f(x)=0$$$ для $$$x \le 2$$$. Заметим, что $$$0$$$ делится на $$$2$$$, поэтому ни одно число $$$x \leq 2$$$ не хорошее.
  • Если $$$x = 3$$$, то $$$\{1,2,3\}$$$ единственная подходящая для Yuzu перестановка. Тогда, $$$f(3)=1$$$, а значит число $$$3$$$ хорошее.
  • Если $$$x = 4$$$, то $$$\{1,2,3\} , \{1,3,2\} , \{2,1,3\} , \{2,3,1\}$$$ это все перестановки, подходящие для Yuzu. Тогда, $$$f(4)=4$$$, значит число $$$4$$$ не хорошее.
  • Если $$$x \ge 5$$$ , все $$$6$$$ перестановок подходят Yuzu. Тогда, $$$f(x)=6$$$ для всех $$$x \ge 5$$$. Значит ни одно число $$$x \ge 5$$$ не хорошее.

Значит единственное хорошее число это $$$3$$$.

В третьем тесте для всех целых положительных $$$x$$$ значение $$$f(x)$$$ делится на $$$p = 3$$$.