#P2167. Irrelevant Elements

Irrelevant Elements

描述

年轻的密码分析员乔治正在研究生成从0到m-1范围内的随机整数的不同方案。他认为标准的随机数生成器不够好,因此他发明了自己的方案,旨在为生成的数字带来更多的随机性。

首先,乔治选择n并生成n个从0到m-1的随机整数。设生成的数字为a1a₁, a2a₂, ......, anaₙ。之后,乔治计算所有相邻数字对的和,并用这些和替换初始数组,从而得到n1n-1个数字:a1+a2,a2+a3,...,an1+ana₁ + a₂, a₂ + a₃, ..., aₙ₋₁ + aₙ。然后他对新数组重复同样的过程,得到n-2个数字。重复这一过程,直到只剩下一个数字。这个数字最后对m取模,即为生成过程的结果。

乔治自豪地向他的计算机科学老师展示了这一方案,但老师指出该方案存在许多缺陷。其中一个重要缺陷是,该过程的结果有时甚至不依赖于初始生成的某些数字。例如,当n=3n=3m=2m=2时,结果不依赖于a2a₂

现在乔治想研究这一现象。如果生成过程的结果不依赖于aiaᵢ,他将初始数组的第ii个元素称为无关元素。他考虑了不同的nnmm,并想知道对于这些参数哪些元素是无关的。请你帮助他找出答案。

输入

输入包含nnmm1n1000002m109(1 ≤ n ≤ 100000,2 ≤ m ≤ 10⁹)

输出

第一行输出给定nnmm时初始数组中无关元素的数量。第二行按升序输出所有满足条件的i,数字之间用空格分隔。