P11135 [MX-X5-T7] "GFOI Round 1" Der Richter

Original problem link: 。 --- > [Der Richter - Ωμεγα](https://www.bilibili.com/video/BV11SpberEjC/)

First, we give some definitions for this problem. A permutation $p_1, p_2, \ldots, p_n$ of $1 \sim n$ is called **good** if and only if $\exists k \in [1, n - 1], \max\limits_{i = 1}^k p_i = k$。 A sequence $x_1, x_2, \ldots, x_k$ is called a **swap plan** of a permutation $p_1, p_2, \ldots, p_n$ if and only if: - $\forall 1 \le i \le k$, $1 \le x_i \le n - 1$ and $x_i$ is an integer； - After performing, **in order**, the operation of swapping the numbers at positions $x_i$ and $x_i + 1$ in $p$ for all $i = 1 \sim k$, $p$ becomes **good**. In particular, the sequence $x$ can be empty, meaning no swaps are performed. A sequence $x_1, x_2, \ldots, x_k$ is called a **critical swap plan** of a permutation $p_1, p_2, \ldots, p_n$ if and only if: - $x$ is a **swap plan** of $p$； - Among all **swap plans** of $p$, $x$ has the minimum length. Let $f(p)$ be the number of distinct **critical swap plans** of the permutation $p$。 A permutation $q$ is called a **final state** of another permutation $p$ if and only if: - $p$ and $q$ have the same length； - $q$ is **good**； - There exists a **critical swap plan** $x_1, x_2, \ldots, x_k$ of $p$ such that after performing, **in order**, the operation of swapping the numbers at positions $x_i$ and $x_i + 1$ in $p$ for all $i = 1 \sim k$, $p$ becomes identical to $q$ (i.e. $\forall 1 \le i \le |p|, p_i = q_i$)。 A permutation $p$ is called **super good** if and only if there exists **exactly one** permutation $q$ such that $q$ is a **final state** of $p$。 Given a **prime** $P$ and $q$ queries, each query gives two integers $n, m$. You need to construct any **super good** permutation $p$ of length $n$ over $1 \sim n$ such that $f(p) \equiv m \pmod P$, or report that there is no solution. This problem will use a **custom checker** to verify whether your constructed permutation is correct, i.e. if a solution exists, outputting any permutation that satisfies the requirements will be accepted.

The first line contains two positive integers $q, P$, representing the number of queries and the modulus. The next $q$ lines each contain two integers $n, m$。

For each query: - If there is no solution, output one line with a single integer $-1$； - Otherwise, output one line with $n$ integers, representing any valid permutation $p_1, p_2, \ldots, p_n$ of $1 \sim n$。 This problem will use a **custom checker** to verify whether your constructed permutation is correct, i.e. if a solution exists, outputting any permutation that satisfies the requirements will be accepted.

**Sample Explanation** For the first query, the permutation $p = [4, 1, 5, 3, 2]$ has only one **critical swap plan** $x = [1]$, and since the only **final state** of $p$ is $q = [1, 4, 5, 3, 2]$, $p$ is **super good**。 For the second query, the permutation $p = [5, 4, 3, 2, 1, 6]$ has only one **critical swap plan** $x = []$, and since the only **final state** of $p$ is $q = [5, 4, 3, 2, 1, 6]$, $p$ is **super good**。 For the third query, the permutation $p = [3, 6, 2, 5, 1, 4]$ has two **critical swap plans** $x = [2, 4, 3]$ and $x = [4, 2, 3]$, and since the only **final state** of $p$ is $q = [3, 2, 1, 6, 5, 4]$, $p$ is **super good**。 **Constraints** **This problem uses bundled testdata.** | Subtask ID | $n \le$ | Special Property | Score | | :-: | :-: | :-: | :-: | | $1$ | $8$ | None | $17$ | | $2$ | $50$ | A | $3$ | | $3$ | $50$ | B | $3$ | | $4$ | $18$ | None | $19$ | | $5$ | $40$ | None | $16$ | | $6$ | $50$ | None | $9$ | | $7$ | $60$ | None | $10$ | | $8$ | $70$ | None | $11$ | | $9$ | $80$ | None | $12$ | - Special property A: $m = 0$。 - Special property B: $m = 1$。 For all testdata, $1 \le q \le 10^4$, $9 \times 10^8 < P < 10^9$, $2 \le n \le 80$, $0 \le m < P$, and $P$ is **prime**。 Translated by ChatGPT 5