Codeforces Round 765 (Div. 2)
D
Binary Spiders
Codeforces
2300
原题
← CE1 →
翻译中…

Binary Spiders are species of spiders that live on Mars. These spiders weave their webs to defend themselves from enemies.

翻译中…

To weave a web, spiders join in pairs. If the first spider in pair has $x$ legs, and the second spider has $y$ legs, then they weave a web with durability $x \oplus y$. Here, $\oplus$ means bitwise XOR.

翻译中…

Binary Spiders live in large groups. You observe a group of $n$ spiders, and the $i$-th spider has $a_i$ legs.

翻译中…

When the group is threatened, some of the spiders become defenders. Defenders are chosen in the following way. First, there must be at least two defenders. Second, any pair of defenders must be able to weave a web with durability at least $k$. Third, there must be as much defenders as possible.

翻译中…

Scientists have researched the behaviour of Binary Spiders for a long time, and now they have a hypothesis that they can always choose the defenders in an optimal way, satisfying the conditions above. You need to verify this hypothesis on your group of spiders. So, you need to understand how many spiders must become defenders. You are not a Binary Spider, so you decided to use a computer to solve this problem.

翻译中…

Input

翻译中…

The first line contains two integers $n$ and $k$ ($2 \le n \le 3\cdot10^5$, $0 \le k \le 2^{30} - 1$), the amount of spiders in the group and the minimal allowed durability of a web.

翻译中…

The second line contains $n$ integers $a_i$ ($0 \le a_i \le 2^{30}-1$) — the number of legs the $i$-th spider has.

翻译中…

Output

翻译中…

In the first line, print a single integer $\ell$ ($2 \le \ell \le n$), the maximum possible amount of defenders.

翻译中…

In the second line, print $\ell$ integers $b_i$, separated by a single space ($1 \le b_i \le n$) — indices of spiders that will become defenders.

翻译中…

If there exists more than one way to choose the defenders, print any of them.

翻译中…

Unfortunately, it may appear that it's impossible to choose the defenders. In this case, print a single integer $-1$.

翻译中…

Note

翻译中…

Consider the examples above.

翻译中…

In the first example, the group of spiders is illustrated on the picture below:

翻译中…

image

翻译中…

We choose the two-legged, the ten-legged and the $16$-legged spiders. It's not hard to see that each pair may weave a web with enough durability, as $2 \oplus 10 = 8 \ge 8$, $2 \oplus 16 = 18 \ge 8$ and $10 \oplus 16 = 26 \ge 8$.

翻译中…

This is not the only way, as you can also choose, for example, the spiders with indices $3$, $4$, and $6$.

翻译中…

In the second example, no pair of spiders can weave the web with durability $1024$ or more, so the answer is $-1$.

翻译中…

样例

Input #1
6 8
2 8 4 16 10 14
Output #1
3
1 5 4
InputCopy OutputCopy
Input #2
6 1024
1 2 3 1 4 0
Output #2
-1
InputCopy OutputCopy
题目信息
题号
1625D
时间限制
2 s
内存限制
256 MB
标签
位运算
数据结构
模拟
数学
排序
树

题面与样例版权归 Codeforces 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。