Background

Original problem link: https://oier.team/problems/X5H。

Der Richter - Ωμεγα

Problem Description

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.

Input Format

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$。

Output Format

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.

5 998244353
5 1
6 1
6 2
6 3
10 20

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

Hint

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.

• 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