P3599 Koishi Loves Construction

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.

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.

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.

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