题目描述

You are given $2n$ integers $b_1, b_2, \dots, b_{2n}$ and an integer $x$. For all $i$, it holds that $1 \le b_i \le x$.

In one operation, you may choose any index $i$ ($1 \le i \le 2n$) and increase the number $b_i$ by $1$.

You need to perform no more than $\left\lfloor \frac{x}{2} \right\rfloor$ operations and split all numbers into $n$ pairs so that in each pair, after performing the operations, one number is divisible by the other.

In other words, you need to find non-negative integers $d_1, d_2, \dots, d_{2n}$ and a partition of the indices $1, 2, \dots, 2n$ into $n$ pairs such that:

• $\sum\limits_{i=1}^{2n} d_i \le \left\lfloor \frac{x}{2} \right\rfloor$, that is, the sum of all $d_i$ does not exceed $\frac{x}{2}$ rounded down;
• if $c_i = b_i + d_i$, then for every pair of indices $(u, v)$, either $c_u \mid c_v$ or $c_v \mid c_u$, that is, either $c_u$ divides $c_v$ or $c_v$ divides $c_u$.

It is guaranteed that for the given constraints, an answer always exists.

$\left\lfloor y \right\rfloor$ denotes the greatest integer not exceeding $y$. For example, $\left\lfloor 7/2 \right\rfloor = 3$.

输入格式

The first line contains one integer $t$ $(1 \le t \le 10^4)$ --- the number of test cases.

Each test case consists of two lines.

The first line of a test case contains two integers $n$ and $x$ ($1 \le n \le 10^5$, $1 \le x \le 10^9$).

The second line contains $2n$ integers $b_1, b_2, \dots, b_{2n}$ ($1 \le b_i \le x$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

输出格式

For each test case, output the answer in the following format.

First, output $n$ lines. In the $j$-th of them, output two integers $u_j$ and $v_j$ --- the indices of the numbers that form the $j$-th pair.

Each index from $1$ to $2n$ must appear in exactly one pair.

After that, output one line with $2n$ integers $d_1, d_2, \dots, d_{2n}$, where $d_i$ is the number of operations performed on the number $b_i$.

The following must hold: $d_i \ge 0$ for all $1 \le i \le 2n$, and also $\sum\limits_{i=1}^{2n} d_i \le \left\lfloor \frac{x}{2} \right\rfloor.$

Let $c_i = b_i + d_i$. For each printed pair $(u_j, v_j)$, it must hold that: $c_{u_j} \mid c_{v_j} \quad \text{or} \quad c_{v_j} \mid c_{u_j}.$

If there are multiple correct answers, you may output any of them.

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

提示

In the first example, we can split the numbers into pairs $(3, 3)$, $(1, 8)$, $(4, 2)$, and $(5, 5)$. In each pair, one number is divisible by the other, so we do not perform any operations.

In the second example, we add $3$ to the first number and $1$ to the last one. We obtain the new array: $[10, 2, 6, 3, 5, 9]$. After that, we split the numbers into pairs $(2, 6)$, $(3, 9)$, and $(10, 5)$. The total number of operations is $3+1 = 4 \leq \left\lfloor \frac{x}{2} \right\rfloor = 4$. Note that this is not the minimum possible number of operations.

Scoring

• ($6$ points): $t = 1$, $n \le 4$, $b_i \le 50$.
• ($7$ points): $t = 1$, $n \le 10$, $b_i \le 10^4$.
• ($7$ points): $t = 1$, $n \le 10$.
• ($10$ points): $b_i \ge \left\lceil \frac{x}{2} \right\rceil$ for all $i$.
• ($10$ points): for each $i$, either $b_i \le \left\lfloor \frac{x}{6} \right\rfloor$ or $b_i \ge x - \left\lfloor \frac{x}{6} \right\rfloor$.
• ($10$ points): the answer can be obtained without performing any operations. All numbers are powers of prime numbers, all numbers do not exceed $10^6$, $t \le 10$.
• ($13$ points): the answer can be obtained without performing any operations. Each number is a product of at most two prime numbers, each prime number appears in the factorization of all numbers in total at most twice, all numbers do not exceed $10^6$, $t \le 10$.
• ($17$ points): There exists an answer where the adjacent numbers of the initial array can be paired: $(1, 2), (3, 4), \ldots, (2n - 1, 2n)$. Also, $\sum n \le 1000$ and $b_i \le 10^9$.
• ($20$ points): no additional constraints.