[SDOI2017]遗忘的集合

题目描述

小Q在他的个人主页上放出了一个悬赏:征集只含正整数的非空集合$S$ ,其中的每个元素都不超过$n$ ,并且满足一些附加条件。 众所周知,我们可以很轻松地对于任意不超过$n$的正整数$x$,计算出把$x$表示成$S$中元素之和的方案数$f(x)$,在这里我们约定,在任意方案中每个数字可以出现多次,但是不考虑数字出现的顺序。 例如,当$S=\{1,2,3,4,5\}$时,我们可以计算出$f(2) = 2, f(3) = 3, f(4) = 5, f(5) = 7$。 再例如,当$S=\{1,2,5\}$时,我们可以计算出$f(4) = 3, f(5) = 4, f(6) = 5, f(7) = 6$。 麻烦地是现在小Q忘记了$S$里有哪些元素,幸运地是他用存储设备记录下了所有$f(i) \mathrm{\ mod\ } p$的值,小Q希望你能利用这些信息帮他恢复出$S$原来的样子。 具体来说,他希望你找到这样一个正整数的**非空**集合$S$,其中的每个元素都不超过$n$,并且对于任意的$i = 1, 2,\cdots ,n$,满足把$i$表示成$S$中元素之和的方案数在模$p$意义下等于$f(i)$,其中$p$是记录在存储设备中的一个质数。他向你保证:**一定存在**这样的集合$S$ 。 然而,小Q觉得他存储的信息并不足以恢复出唯一的$S$,也就是说,可能会存在多个这样的集合$S$,所以小Q希望你能给出所有解中**字典序最小**的解。 对于满足条件的两个不同的集合$S_1$和$S_2$,我们认为$S_1$的字典序比$S_2$的字典序小,当且仅当存在非负整数$k$,使得$S_1$的前$k$小元素与$S_2$的前$k$小元素完全相等,并且,要么$S_1$的元素个数为$k$,且$S_2$的元素个数至少为$(k + 1)$,要么$S_1$和$S_2$都有至少$(k + 1)$个元素,且$S_1$的第$(k + 1)$小元素比$S_2$的第$(k + 1)$小元素小。

输入输出格式

输入格式


第一行包含两个整数$n$和$p$,满足$p$是质数。 第二行包含$n$个整数$f(1), f(2),\cdots , f(n)$ ,含义见题目描述。 保证每一行中相邻的整数由恰好一个空格隔开,并且末尾没有多余的空格。

输出格式


你需要输出两行信息来描述字典序最小的解,其中第一行包含一个整数$m (m > 0)$,表示$S$的元素个数,第二行包含$m$个正整数$s_1, s_2,\cdots ,s_m$,表示将$S$的所有元素按升序排序后得到的序列。 你需要保证输出的每一行中相邻的整数由恰好一个空格隔开,并且每一行的末尾没有多余的空格。

输入输出样例

输入样例 #1

5 1000003
1 2 3 5 7

输出样例 #1

5
1 2 3 4 5

输入样例 #2

9 1000003
1 2 2 3 4 5 6 7 8

输出样例 #2

3
1 2 5

说明

对于$100\%$的数据,有$1 \leq n < 2^{18} , 10^6 \leq p < 2^{30} , 0 \leq f(i) < p (i=1,2, \cdots , n)$。 ![](https://cdn.luogu.com.cn/upload/pic/5548.png)