假设您有 $$$n$$$ 个盒子。第 $$$i$$$ 个盒子包含无限多个颜色 $$$i$$$ 的球。有时你需要得到一个特定颜色的球;但你又懒得自己做。
您已经购买了两个机器人来为您取回球。现在你必须对它们进行编程。为了对机器人进行编程,您必须构建两个列表 $$$[a_1, a_2, \dots, a_k]$$$ 和 $$$[b_1, b_2, \dots, b_{n-k}]$$$,其中列表 $$$a$$$ 表示分配给第一个机器人的框,列表 $$$b$$$ 表示分配给第二个机器人的框。从 $$$1$$$ 到 $$$n$$$ 的每个整数都必须恰好出现在这些列表之一中。
当您请求颜色为 $$$x$$$ 的球时,机器人将按如下方式工作。每个机器人按照列表中出现的顺序查看分配给该机器人的框。第一个机器人花费 $$$s_1$$$ 秒分析盒子中的内容;第二个机器人花费 $$$s_2$$$。一旦其中一个机器人找到装有 $$$x$$$ 颜色球的盒子(并分析其内容),搜索就会结束。搜索时间是从搜索开始到其中一个机器人完成分析第 $$$x$$$ 个盒子内容的秒数。如果机器人分析了分配给它的所有盒子的内容,它就会停止搜索。
例如,假设 $$$s_1 = 2$$$、$$$s_2 = 3$$$、$$$a = [4, 1, 5, 3, 7]$$$、$$$b = [2, 6]$$$。如果您请求颜色为 $$$3$$$ 的球,则会发生以下情况:
- 最初,第一个机器人开始分析盒子$$$4$$$,第二个机器人开始分析盒子$$$2$$$;
- 在$$$2$$$第二秒结束时,第一个机器人完成对盒子$$$4$$$的分析。这不是你需要的盒子,所以机器人继续盒子$$$1$$$;
- 在第 $$$3$$$-rd 秒结束时,第二个机器人完成对盒子 $$$2$$$ 的分析。这不是你需要的盒子,所以机器人继续盒子$$$6$$$;
- 在第$$$4$$$秒结束时,第一个机器人完成对盒子$$$1$$$的分析。这不是你需要的盒子,所以机器人继续盒子$$$5$$$;
- 在第$$$6$$$秒结束时,第一个机器人完成对盒子$$$5$$$的分析。这不是您需要的盒子,因此机器人继续处理盒子$$$3$$$。与此同时,第二个机器人完成了盒子$$$6$$$的分析。不是您需要的盒子,并且第二个机器人已分析了其列表中的所有盒子,因此机器人停止搜索;
- 在第$$$8$$$秒结束时,第一个机器人完成对盒子$$$3$$$的分析。正是你需要的盒子,所以搜索结束;
- 因此,搜索时间为 $$$8$$$ 秒。
您知道您将请求一个颜色球 $$$1$$$ $$$r_1$$$ 次,一个颜色球 $$$2$$$ $$$r_2$$$ 次,依此类推。您希望为机器人构造 $$$a$$$ 和 $$$b$$$ 列表,以使所有请求的总搜索时间尽可能最小。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例由两行组成:
- 第一行包含三个整数 $$$n$$$, $$$s_1$$$, $$$s_2$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$1 \le s_1, s_2 \le 10$$$);
- 第二行包含 $$$n$$$ 整数 $$$r_1, r_2, \dots, r_n$$$ ($$$1 \le r_i \le 10^6$$$)。
对输入的附加约束:所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印两行。第一行应包含列表 $$$a$$$,第二行应包含列表 $$$b$$$。每个列表都必须按如下方式打印:首先,打印其中的元素数量,然后打印元素本身。
如果有多个答案,您可以打印其中任何一个。
示例
输入 #1
3 7 3 1 8 6 4 4 4 1 7 5 1 10 1 1 1 1 1 8 1 1 4 5 6 8 1 7 3 2
输出 #1
2 5 6 5 1 7 2 4 3 5 4 3 5 2 1 0 4 4 2 7 5 4 6 3 1 8