Unique Pairwise XOR Sidon Set

Given a positive even integer (N), consider the set (U = {0,1,\dots,2^{N}-1}), where the binary representation of every element has exactly (N) bits. We call a subset (S \subseteq U) a Sidon set for XOR if for every two distinct unordered pairs ((a,b)) and ((c,d)) (with (a<b,, c<d,) and ({a,b}\neq{c,d})) it holds that [ a \oplus b \neq c \oplus d,] where (\oplus) denotes the bitwise XOR. Equivalently, the (\binom{|S|}{2}) pairwise XOR values are all distinct.

It can be shown that when (N) is even, one can construct a Sidon set (S) of maximum size (|S| = 2^{N/2}+ {\bf \varepsilon}). (In fact, for (N=2) one may achieve (|S|=3), and for larger even (N) a known construction attains size (2^{N/2}+1).)

One such construction is as follows. Write every number (x\in U) in binary as a concatenation (x = (u,v)) where both (u) and (v) have (N/2) bits. For (N/2 = m = 1) (i.e. (N=2)) one may simply take (S = {0,1,2}) (here, in binary: 00, 01, and 10) which can be verified to be a Sidon set. For (m\ge 2), view (u) and (v) as elements of the finite field (\mathbb{F}{2^m}). By selecting a suitable non‐linear permutation (f:,\mathbb{F}{2^m}\to \mathbb{F}{2^m}) (for example, by choosing an exponent (k\ge3) with (\gcd(k,2^m-1)=1) – note that one may choose (k=3) when (m) is odd and, when (m) is even, a small candidate such as (k=5) or (7) which does not share factors with (2^m-1) – so that (f(x)=x^k) is a permutation on (\mathbb{F}{2^m}) but non-linear) we define [ S = \Big{ (x, f(x)) : x \in \mathbb{F}_{2^m} \Big} \cup { (0,1) }. ] Then interpreting each pair ((x,y)) as the (N)-bit integer (x \ll m ;|; y) (with the first (m) bits given by (x) and the last (m) bits by (y)), one obtains a Sidon set of size (2^m+1 = 2^{N/2}+1).

Your task is to implement this construction. That is, given (N) (which is even) as input, output a Sidon set (S) (as described above) in increasing order. The output format is as follows: On the first line, print the size (|S|). On the second line print the elements of (S) (in increasing order) separated by a space.

Note: For (N=2) (i.e. (m=1)) the set (S = {0,1,2}) is acceptable. For (m \ge 2), you will need to perform arithmetic in (\mathbb{F}{2^m}). You may use a hard‐coded irreducible polynomial for (\mathbb{F}{2^m}) for small (m). For example, for (m=2,3,4,\dots) you can use the irreducible polynomials with binary representations 111 (for (m=2)), 1011 (for (m=3)), 10011 (for (m=4)), etc.

It is guaranteed that the input (N) is even and sufficiently small so that the above construction can be implemented.

inputFormat

The input consists of a single line containing an even positive integer (N) (where (N\ge2)).

outputFormat

First, output the size of the constructed Sidon set (S) on a single line. On the next line, output all elements of (S) in increasing order, separated by a single space.

sample

2

3
0 1 2