Description

Koishi decided to leave Gensokyo and become a math master!

Flandre heard that her math is excellent, so she gave Koishi the following construction problem:

Task 1: Determine whether it is possible, and if so construct, a permutation of $1 \dots n$ of length $n$ such that its $n$ prefix sums are pairwise distinct modulo $n$.

Task 2: Determine whether it is possible, and if so construct, a permutation of $1 \dots n$ of length $n$ such that its $n$ prefix products are pairwise distinct modulo $n$.

As usual, Koishi pretended she could not do it and came to ask you for help.

Input Format

The first line contains two integers $X$ and $T$, denoting the task type and the number of test cases in the test point, respectively.

Then follow $T$ lines, each containing one integer $n$ for a test case.

Output Format

For the convenience of the SPJ, you must follow the format below.

For each test case, output exactly one line:

1. If you believe no valid construction exists, output a single integer $0$.
2. If you believe a valid construction exists but you cannot construct it, output a single integer $1$.
3. If you believe a valid construction exists and you successfully construct it, first output a single integer $2$, then output $n$ integers giving your construction.

Separate every two integers with a space.

1 1
8

2 8 7 6 5 4 3 2 1

2 1
11

2 1 2 3 5 10 6 7 4 9 8 11

Hint

For each test case:

1. If your existence judgment is correct, you will receive $30\%$ of the score. If your construction satisfies the requirements or there truly is no valid construction, you will receive the remaining $70\%$.
2. If your existence judgment is incorrect, you will receive no points.

Test point type $1$: $10$ points, with $X = 1$, $1 \leq n \leq 10$. Test point type $2$: $40$ points, with $X = 1$, $1 \leq n \leq {10}^5$. Test point type $3$: $10$ points, with $X = 2$, $1 \leq n \leq 10$. Test point type $4$: $40$ points, with $X = 2$, $1 \leq n \leq {10}^5$.

For all test points, it holds that $1 \leq T \leq 10$.

Translated by ChatGPT 5