← 返回题目列表

Codeforces · 1370/B

B. GCD 压缩

中文机器翻译题面 查看原题

Ashish 有一个数组 $$$a$$$,由 $$$2n$$$ 正整数组成。他想将 $$$a$$$ 压缩到大小为 $$$n-1$$$ 的数组 $$$b$$$ 中。为此,他首先从 $$$a$$$ 中恰好丢弃 $$$2$$$ (任意两个)元素。然后,他执行以下操作,直到 $$$a$$$ 中没有剩余元素为止:

- 从 $$$a$$$ 中删除任意两个元素并将它们的总和附加到 $$$b$$$。

压缩数组 $$$b$$$ 必须具有特殊属性。其所有元素的最大公约数 ($$$\mathrm{gcd}$$$) 应大于 $$$1$$$。

回想一下,正整数数组的 $$$\mathrm{gcd}$$$ 是最大整数,它是数组中所有整数的除数。

可以证明,总是可以将数组$$$a$$$压缩为大小为$$$n-1$$$的数组$$$b$$$,使得$$$gcd(b_1, b_2..., b_{n-1}) > 1$$$。

帮助阿什什找到一种方法来做到这一点。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 1000$$$)。

每个测试用例的第二行包含 $$$2n$$$ 整数 $$$a_1, a_2, \ldots, a_{2n}$$$ ($$$1 \leq a_i \leq 1000$$$) — 数组 $$$a$$$ 的元素。

输出

对于每个测试用例,输出 $$$n-1$$$ 行 - 将数组 $$$a$$$ 压缩到数组 $$$b$$$ 所执行的操作。最初丢弃两个元素不是一个操作,您不需要输出任何有关它的内容。

第 $$$i$$$ 行应包含两个整数,即第 $$$i$$$ 操作中使用的数组 $$$a$$$ 中两个元素的索引(基于 $$$1$$$)。所有 $$$2n-2$$$ 索引应该是从 $$$1$$$ 到 $$$2n$$$ 的不同整数。

您不需要从 $$$a$$$ 输出两个最初丢弃的元素。

如果有多个答案,您可以找到任何一个。

示例

输入 #1

3
3
1 2 3 4 5 6
2
5 7 9 10
5
1 3 3 4 5 90 100 101 2 3

输出 #1

3 6
4 5
3 4
1 9
2 3
4 5
6 10

注意

在第一个测试用例中,$$$b = \{3+6, 4+5\} = \{9, 9\}$$$ 和 $$$\mathrm{gcd}(9, 9) = 9$$$。

在第二个测试用例中,$$$b = \{9+10\} = \{19\}$$$ 和 $$$\mathrm{gcd}(19) = 19$$$。

在第三个测试用例中,$$$b = \{1+2, 3+3, 4+5, 90+3\} = \{3, 6, 9, 93\}$$$ 和 $$$\mathrm{gcd}(3, 6, 9, 93) = 3$$$。