问题陈述
新年的钟声敲响了 等间隔 N 次。 更具体地说,铃声有时会响起 t, d+t, 2d+t, \ldots, (N-1)d+t 对于某个正整数 d 和整数 给出了 t.
高桥有时听到铃声响起 A_1, A_2, \ldots, A_K。 虽然可以肯定的是,当高桥听到声音时,铃声确实响了,但铃声可能在其他时候也响过。
你被给予 N, K,和 A_1, A_2, \ldots, A_K。 列出正整数的所有可能值 d 按升序排列.
在这个问题的约束下,可以证明,可能值的个数 d 是有限的。
约束
- 2 \leq N \leq 10^9
- 2 \leq K \leq \min \lbrace N, 2 \times 10^5 \rbrace
- 0 \leq A_1 \lt A_2 \lt \cdots \lt A_K \leq 10^9
- 所有输入值均为整数。
- 正整数至少有一个可能的值 d.
输入
输入由标准输入按以下格式给出:
N K A_1 A_2 \ldots A_K
输出
列出正整数的所有可能值 d 按以下格式升序排列:
M d_1 d_2 \ldots d_M
也就是说,第一行应包含 M,可能值的数量 d, 第二行应包含 (d_1, d_2, \ldots, d_M),所有可能的值 d 按升序排列,中间有空格。
示例输入 1
8 3 3 7 15
示例输出 1
2 2 4
有两个可能的值 d: 2 和 4.
- 对于 d = 2,例如,有时铃声可能会响八次 3, 5, 7, 9, 11, 13, 15, 17.
- 对于 d = 4,例如,有时铃声可能会响八次 -5, -1, 3, 7, 11, 15, 19, 23.
示例输入 2
500 22 30 42 138 318 354 378 450 462 522 582 630 738 834 894 930 942 1002 1050 1062 1110 1146 1158
示例输出 2
4 3 4 6 12