#ABC134D. Preparing Boxes

Preparing Boxes

题目描述

There are NN empty boxes arranged in a row from left to right. The integer ii is written on the ii-th box from the left (1iN)(1 \leq i \leq N).

For each of these boxes, Snuke can choose either to put a ball in it or to put nothing in it.

We say a set of choices to put a ball or not in the boxes is good when the following condition is satisfied:

  • For every integer ii between 11 and NN (inclusive), the total number of balls contained in the boxes with multiples of ii written on them is congruent to aia_i mod 22.

Does there exist a good set of choices? If the answer is yes, find one good set of choices.

NN 个空盒子,从左到右排成一行。整数 ii 写在左起 (1iN)(1 \leq i \leq N) 的第 ii 个盒子上。

对于每一个盒子,斯努克都可以选择放一个球或者什么都不放。

当满足以下条件时,我们说一组放球或不放球的选择是好的:

  • 对于介于 11NN (含)之间的每一个整数 ii ,写有 ii 倍数的盒子中包含的球的总数与 aia_i 同余,模为 22

是否存在一组好的选择?如果答案是肯定的,请找出一组好的选择。

输入格式

输入内容按以下格式标准输入:

NN
a1a_1 a2a_2 ...... aNa_N

输出格式

如果不存在一组好的选择,则打印 -1

如果存在一组好的选择,则按以下格式打印一组这样的选择:

$M$  
$b_1$ $b_2$ $...$ $b_M$  

其中 MM 表示将包含一个小球的盒子数量, b1, b2, ..., bMb_1,\ b_2,\ ...,\ b_M 是写在这些盒子上的整数,顺序不限。

样例 #1

样例输入 #1

3
1 0 0

样例输出 #1

1
1

样例 #2

样例输入 #2

5
0 0 0 0 0

样例输出 #2

0

说明

数据规模与约定

  • 所有输入值均为整数。
  • 1N2×1051 \leq N \leq 2 \times 10^5
  • aia_i0011

样例 11 解释

考虑只在写有 11 的盒子里放一个球。

  • 有三个盒子上写着 11 的倍数: 112233 。这些盒子中包含的球的总数是 11
  • 只有一个盒子上写着 22 的倍数:写着 22 的盒子。这些盒子中包含的球的总数是 00
  • 只有一个盒子上写有 33 的倍数:写有 33 的盒子。这些盒子中包含的球的总数是 00

因此,条件满足,所以这组选择是好的。

样例 22 解释

在方框中什么都不放也是一组不错的选择。