ID: 7565 Type: RemoteJudge 4000ms 256MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>constructive algorithmshashingnumber theory

## Description

Let's call a set of positive integers \$a_1, a_2, \dots, a_k\$ quadratic if the product of the factorials of its elements is a square of an integer, i. e. \$\prod\limits_{i=1}^{k} a_i! = m^2\$, for some integer \$m\$.

You are given a positive integer \$n\$.

Your task is to find a quadratic subset of a set \$1, 2, \dots, n\$ of maximum size. If there are multiple answers, print any of them.

A single line contains a single integer \$n\$ (\$1 \le n \le 10^6\$).

In the first line, print a single integer — the size of the maximum subset. In the second line, print the subset itself in an arbitrary order.

## Input

A single line contains a single integer \$n\$ (\$1 \le n \le 10^6\$).

## Output

In the first line, print a single integer — the size of the maximum subset. In the second line, print the subset itself in an arbitrary order.

## Samples

``````1
``````
``````1
1
``````
``````4
``````
``````3
1 3 4
``````
``````7
``````
``````4
1 4 5 6
``````
``````9
``````
``````7
1 2 4 5 6 7 9
``````