[Solution] Circular Xor Reversal Codeforces Solution

F. Circular Xor Reversal

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You have an array 𝑎0,𝑎1,…,𝑎𝑛−1$a_0,a_1,\dots ,a_{n-1}$ of length 𝑛$n$. Initially, 𝑎𝑖=2𝑖$a_i=2^i$ for all 0≤𝑖<𝑛$0\le i<n$. Note that array 𝑎$a$ is zero-indexed.

You want to reverse this array (that is, make 𝑎𝑖$a_i$ equal to 2𝑛−1−𝑖$2^{n-1-i}$ for all 0≤𝑖<𝑛$0\le i<n$). To do this, you can perform the following operation no more than 250000$250000$ times:

• Select an integer 𝑖$i$ (0≤𝑖<𝑛$0\le i<n$) and replace 𝑎𝑖$a_i$ by 𝑎𝑖⊕𝑎(𝑖+1)mod𝑛$a_i\oplus a_{(i+1)modn}$.

Here, ⊕$\oplus$ denotes the bitwise XOR operation.

Your task is to find any sequence of operations that will result in the array 𝑎$a$ being reversed. It can be shown that under the given constraints, a solution always exists.

Input

The first line contains a single integer 𝑛$n$ (2≤𝑛≤400$2\le n\le 400$) — the length of the array 𝑎$a$.

Output

On the first line print one integer 𝑘$k$ (0≤𝑘≤250000$0\le k\le 250000$) — the number of operations performed.

On the second line print 𝑘$k$ integers 𝑖1,𝑖2,…,𝑖𝑘$i_1,i_2,\dots ,i_k$ (0≤𝑖𝑗<𝑛$0\le i_j<n$). Here, 𝑖𝑗$i_j$ should be the integer selected on the 𝑗$j$-th operation.

Note that you don't need to minimize the number of operations.

Note

In the notes, the elements on which the operations are performed are colored red.

In the first test case, array 𝑎$a$ will change in the following way:

[1,2]→[1,3]→[2,3]→[2,1]$[1,2]\to [1,3]\to [2,3]\to [2,1]$.

In the second test case, array 𝑎$a$ will change in the following way: