题目背景

Der Richter - Ωμεγα

题目描述

我们首先给出关于本题的一些定义。

定义一个 $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$		B
$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$ 是质数。