题目描述

给定 $2n$ 个整数 $b_1, b_2, \dots, b_{2n}$ 和一个整数 $x$。对于所有 $i$，满足 $1 \le b_i \le x$。

在一次操作中，你可以选择任意下标 $i$ ($1 \le i \le 2n$)，并将该数 $b_i$ 增加 $1$。

你需要执行不超过 $\left\lfloor \frac{x}{2} \right\rfloor$ 次操作，并将所有数分成 $n$ 对，使得在操作完成后，每对中一个数能被另一个数整除。

换句话说，你需要找到非负整数 $d_1, d_2, \dots, d_{2n}$ 以及下标 $1, 2, \dots, 2n$ 的一个 $n$ 对划分，使得：

• $\sum\limits_{i=1}^{2n} d_i \le \left\lfloor \frac{x}{2} \right\rfloor$，即所有 $d_i$ 之和不超过 $\frac{x}{2}$ 向下取整的值；
• 若记 $c_i = b_i + d_i$，则对于每一对下标 $(u, v)$，要么 $c_u \mid c_v$，要么 $c_v \mid c_u$，即 $c_u$ 整除 $c_v$ 或 $c_v$ 整除 $c_u$。

保证在给定的约束下，答案总是存在。

$\left\lfloor y \right\rfloor$ 表示不超过 $y$ 的最大整数。例如，$\left\lfloor 7/2 \right\rfloor = 3$。

输入格式

第一行包含一个整数 $t$ $(1 \le t \le 10^4)$ —— 测试数据的组数。

每组测试数据包含两行。

测试数据的第一行包含两个整数 $n$ 和 $x$ ($1 \le n \le 10^5$, $1 \le x \le 10^9$)。

第二行包含 $2n$ 个整数 $b_1, b_2, \dots, b_{2n}$ ($1 \le b_i \le x$)。

保证所有测试数据的 $n$ 之和不超过 $10^5$。

输出格式

对于每组测试数据，按以下格式输出答案。

首先，输出 $n$ 行。在第 $j$ 行中，输出两个整数 $u_j$ 和 $v_j$ —— 组成第 $j$ 对的两个数的原始下标。

每个从 $1$ 到 $2n$ 的下标必须在所有对中恰好出现一次。

然后，输出一行包含 $2n$ 个整数 $d_1, d_2, \dots, d_{2n}$，其中 $d_i$ 是对数字 $b_i$ 执行的操作次数。必须满足：对于所有 $1 \le i \le 2n$，有 $d_i \ge 0$，并且 $\sum\limits_{i=1}^{2n} d_i \le \left\lfloor \frac{x}{2} \right\rfloor$。

令 $c_i = b_i + d_i$。对于输出的每一对 $(u_j, v_j)$，必须满足：$c_{u_j} \mid c_{v_j}$ 或 $c_{v_j} \mid c_{u_j}$。

如果存在多个正确答案，你可以输出其中任意一个。

2
4 8
3 1 4 2 5 3 8 5
3 8
7 2 6 3 5 8

1 6
2 7
3 4
5 8
0 0 0 0 0 0 0 0
2 3
4 6
1 5
3 0 0 0 0 1

提示

在第一个例子中，我们可以将数字分成对 $(3, 3)$、$(1, 8)$、$(4, 2)$ 和 $(5, 5)$。每一对中，一个数都能被另一个整除，因此我们不需要执行任何操作。

在第二个例子中，我们将第一个数增加 $3$，最后一个数增加 $1$。我们得到新的数组：$[10, 2, 6, 3, 5, 9]$。随后，我们将数字分成对 $(2, 6)$、$(3, 9)$ 和 $(10, 5)$。操作总次数为 $3 + 1 = 4 \le \left\lfloor \frac{x}{2} \right\rfloor = 4$。注意，这并非可能的最少操作次数。

计分

• ($6$ 分)：$t = 1$，$n \le 4$，$b_i \le 50$。
• ($7$ 分)：$t = 1$，$n \le 10$，$b_i \le 10^4$。
• ($7$ 分)：$t = 1$，$n \le 10$。
• ($10$ 分)：对于所有 $i$，有 $b_i \ge \left\lceil \frac{x}{2} \right\rceil$。
• ($10$ 分)：对于每个 $i$，要么 $b_i \le \left\lfloor \frac{x}{6} \right\rfloor$，要么 $b_i \ge x - \left\lfloor \frac{x}{6} \right\rfloor$。
• ($10$ 分)：可以不执行任何操作就得到答案。所有数都是素数的幂，所有数不超过 $10^6$，$t \le 10$。
• ($13$ 分)：可以不执行任何操作就得到答案。每个数都是至多两个素数的乘积，每个素数在所有数的分解中总共出现至多两次，所有数不超过 $10^6$，$t \le 10$。
• ($17$ 分)：存在一个答案，使得初始数组的相邻数可以两两配对：$(1, 2), (3, 4), \ldots, (2n - 1, 2n)$。同时 $\sum n \le 1000$ 且 $b_i \le 10^9$。
• ($20$ 分)：无额外限制。

翻译由 DeepSeek V4 Pro 完成