P3784 [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)\bmod 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)$ 小元素小。

无

无

对于 $100\%$ 的数据，有 $1 \leq n < 2^{18} , 10^6 \leq p < 2^{30} , 0 \leq f(i) < p\quad (i=1,2, \cdots , n)$。