← 返回题目列表

Codeforces · 2108/B

B. 总和分解

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

在最近的一个生日那天,你最好的朋友 Maurice 给了你一对数字 $$$n$$$ 和 $$$x$$$,并要求你构建一个数组 积极 长度为 $$$n$$$ 的数字 $$$a$$$ 使得 $$$a_1 \oplus a_2 \oplus \cdots \oplus a_n = x$$$ $$$^{\text{*}}$$$。

这个任务对你来说太简单了,因此你决定给莫里斯一份回礼,在所有这些数组中构造一个元素和最小的数组。你立刻想到了一个合适的数组;然而,由于将其写下来太耗时,莫里斯将不得不满足于仅将其元素的总和。

$$$^{\text{*}}$$$$$$\oplus$$$ 表示按位异或运算。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例由一行组成,其中包含一对数字 $$$n$$$ 和 $$$x$$$ ($$$1 \le n \le 10^9, \; 0 \le x \le 10^9$$$) - Maurice 给您的数字。

输出

对于每个测试用例,输出你给莫里斯的礼物——满足所有描述属性的数组元素的总和。如果不存在合适的数组,则输出$$$-1$$$。

示例

输入
复制

8
2 1
3 6
1 0
2 0
5 0
2 27
15 43
12345678 9101112

输出
复制

5
8
-1
2
8
27
55
21446778

注意

在第一个测试用例中,合适的数组之一是 $$$[2, 3]$$$。可以看出,不可能实现更小的数组元素之和。

在第二种情况下,合适的数组之一是 $$$[1, 3, 4]$$$。还可以证明这是最佳量。