【MX-X5-T7】「GFOI Round 1」Der Richter

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

我们首先给出关于本题的一些定义。 定义一个 $1 \sim n$ 的排列 $p_1, p_2, \ldots, p_n$ 是**好的**，当且仅当 $\exists k \in [1, n - 1], \max\limits_{i = 1}^k p_i = k$。 定义一个序列 $x_1, x_2, \ldots, x_k$ 是一个排列 $p_1, p_2, \ldots, p_n$ 的**交换方案**，当且仅当： - $\forall 1 \le i \le k$，$1 \le x_i \le n - 1$ 且 $x_i$ 是整数； - 对所有 $i = 1 \sim k$ **依次**执行交换 $p$ 中 $x_i$ 和 $x_i + 1$ 位置上的数的操作之后，$p$ 是**好的**。 特别地，序列 $x$ 可以为空，代表不进行任何交换操作。 定义一个序列 $x_1, x_2, \ldots, x_k$ 是一个排列 $p_1, p_2, \ldots, p_n$ 的**关键交换方案**，当且仅当： - $x$ 是 $p$ 的一个**交换方案**； - $x$ 是 $p$ 的所有**交换方案**中长度最小的。 定义 $f(p)$ 为排列 $p$ 的不同的**关键交换方案**的个数。 定义一个排列 $q$ 是另一个排列 $p$ 的一个**终态**，当且仅当： - $p$ 的长度与 $q$ 相等； - $q$ 是**好的**； - 存在一个 $p$ 的**关键交换方案** $x_1, x_2, \ldots, x_k$，使得对所有 $i = 1 \sim k$ **依次**执行交换 $p$ 中 $x_i$ 和 $x_i + 1$ 位置上的数的操作之后，$p$ 与 $q$ 相同（即 $\forall 1 \le i \le |p|, p_i = q_i$）。 定义一个排列 $p$ 是**极好的**，当且仅当只存在**一个**排列 $q$，使得 $q$ 是 $p$ 的**终态**。 给定一个**质数** $P$ 和 $q$ 次询问，每次询问给定两个整数 $n, m$，你需要构造任意一个**极好的**长度为 $n$ 且 $f(p) \equiv m \pmod P$ 的 $1 \sim n$ 的排列 $p$，或报告无解。 本题将使用**自定义校验器**检查你构造的排列是否正确，即若有解输出任意一个满足要求的排列都会被认为通过。

第一行输入两个正整数 $q, P$，表示询问次数和模数。 接下来 $q$ 行，每行包含两个整数 $n, m$。

对于每次询问： - 若无解输出一行一个整数 $-1$； - 否则输出一行 $n$ 个整数，表示任意一个符合要求的 $1 \sim n$ 的排列 $p_1, p_2, \ldots, p_n$。 本题将使用**自定义校验器**检查你构造的排列是否正确，即若有解输出任意一个满足要求的排列都会被认为通过。

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

**【样例解释】** 对于第一次询问，排列 $p = [4, 1, 5, 3, 2]$ 的**关键交换方案**只有 $x = [1]$，且因为 $p$ 的**终态**只有 $q = [1, 4, 5, 3, 2]$ 所以 $p$ 是**极好的**。 对于第二次询问，排列 $p = [5, 4, 3, 2, 1, 6]$ 的**关键交换方案**只有 $x = []$，且因为 $p$ 的**终态**只有 $q = [5, 4, 3, 2, 1, 6]$ 所以 $p$ 是**极好的**。 对于第三次询问，排列 $p = [3, 6, 2, 5, 1, 4]$ 的**关键交换方案**有 $x = [2, 4, 3]$ 和 $x = [4, 2, 3]$，且因为 $p$ 的**终态**只有 $q = [3, 2, 1, 6, 5, 4]$ 所以 $p$ 是**极好的**。 **【数据范围】** **本题采用捆绑测试。** | 子任务编号 | $n \le$ | 特殊性质 | 分值 | | :-: | :-: | :-: | :-: | | $1$ | $8$ | 无 | $17$ | | $2$ | $50$ | A | $3$ | | $3$ | $50$ | B | $3$ | | $4$ | $18$ | 无 | $19$ | | $5$ | $40$ | 无 | $16$ | | $6$ | $50$ | 无 | $9$ | | $7$ | $60$ | 无 | $10$ | | $8$ | $70$ | 无 | $11$ | | $9$ | $80$ | 无 | $12$ | - 特殊性质 A：$m = 0$。 - 特殊性质 B：$m = 1$。 对于所有数据，满足 $1 \le q \le 10^4$，$9 \times 10^8 < P < 10^9$，$2 \le n \le 80$，$0 \le m < P$，$P$ 是**质数**。