← 返回题目列表

Codeforces · 1625/D

D. 二元蜘蛛

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

二元蜘蛛是生活在火星上的蜘蛛种类。这些蜘蛛编织网来防御敌人。

蜘蛛成对结网,结成网。如果成对的第一只蜘蛛有 $$$x$$$ 腿,第二只蜘蛛有 $$$y$$$ 腿,那么它们编织的网具有耐用性 $$$x \oplus y$$$。这里,$$$\oplus$$$ 表示按位异或。

二元蜘蛛生活在大群中。您观察到一群 $$$n$$$ 蜘蛛,第 $$$i$$$ 蜘蛛有 $$$a_i$$$ 腿。

当群体受到威胁时,一些蜘蛛会成为防御者。防守队员的选择方式如下。首先,必须有至少两名防守者。其次,任何一对防守者都必须能够编织出一张耐用性至少为 $$$k$$$ 的网。第三,必须有尽可能多的防守者。

科学家对二元蜘蛛的行为进行了很长时间的研究,现在他们有一个假设,即二元蜘蛛总能以最优的方式选择防御者,满足上述条件。您需要在您的蜘蛛群中验证这个假设。所以,你需要了解有多少蜘蛛必须成为防御者。你不是二元蜘蛛,所以你决定使用计算机来解决这个问题。

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le n \le 3\cdot10^5$$$, $$$0 \le k \le 2^{30} - 1$$$),组中蜘蛛的数量以及蜘蛛网允许的最小耐用性。

第二行包含 $$$n$$$ 整数 $$$a_i$$$ ($$$0 \le a_i \le 2^{30}-1$$$) — 第 $$$i$$$ 个蜘蛛的腿数。

输出

在第一行中,打印一个整数 $$$\ell$$$ ($$$2 \le \ell \le n$$$),即防守者的最大可能数量。

在第二行中,打印 $$$\ell$$$ 整数 $$$b_i$$$,用一个空格分隔 ($$$1 \le b_i \le n$$$) — 将成为防御者的蜘蛛的索引。

如果存在多种选择防守者的方法,则打印其中任何一种。

不幸的是,似乎不可能选择防守者。在本例中,打印单个整数 $$$-1$$$。

示例

输入 #1

6 8
2 8 4 16 10 14

输出 #1

3
1 5 4

输入 #2

6 1024
1 2 3 1 4 0

输出 #2

-1

注意

考虑上面的例子。

在第一个示例中,蜘蛛群如下图所示:

我们选择两足蜘蛛、十足蜘蛛和 $$$16$$$ 足蜘蛛。不难看出,每一对都可以编织出足够耐用的网,如 $$$2 \oplus 10 = 8 \ge 8$$$、$$$2 \oplus 16 = 18 \ge 8$$$ 和 $$$10 \oplus 16 = 26 \ge 8$$$。

这不是唯一的方法,您还可以选择索引为 $$$3$$$、$$$4$$$ 和 $$$6$$$ 的蜘蛛。

在第二个例子中,没有一对蜘蛛能够编织出具有 $$$1024$$$ 或更高耐久度的蜘蛛网,因此答案是 $$$-1$$$。