6689: 等式

内存限制:256 MB 时间限制:2 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:1 通过:0

题目描述

宇宙定律可以由 N 个非负整数组成的数组表示。

数组中的第 i 个数为 Ai

如果存在一个非负整数 k 使得以下等式成立,则宇宙是良好的:

(A1 xor k)+(A2 xor k)+…+(AN xor k)≤M

其中,xor 表示按位异或。

请你求出能够使得宇宙良好的最大的 k 为多少? 

输入格式

第一行包含整数 T,表示共有 T 组测试数据。 

每组测试数据第一行包含两个整数 N 和 M。 

第二行包含 N 个整数,其中第 i 个整数为 Ai。 

输出格式

每组数据输出一个结果,每个结果占一行。  

结果表示为“Case #x: y”,其中x是组别编号(从1开始),y为 k 的最大值,如果 k 不存在,则返回 -1。 

数据范围

1≤T≤100
1≤N≤1000,0≤M≤1015,0≤Ai≤1015

输入样例:

4
3 27
8 2 4
4 45
30 0 4 11
1 0
100
6 2
5 5 1 5 1 0
输出样例:
Case #1: 12
Case #2: 14
Case #3: 100
Case #4: -1

样例解释

在样例#1中,N = 3,M = 27,满足等式的最大的 k 为 12,(8 xor 12) + (2 xor 12) + (4 xor 12) = 26。 

在样例#2中,N = 4,M = 45,满足等式的最大的 k 为 14,(30 xor 14) + (0 xor 14) + (4 xor 14) + (11 xor 14) = 45。 

在样例#3中,N = 1,M = 0,满足等式的最大的 k 为 100,100 xor 100 = 0。 

在样例#4中,没有满足等式的 k 值,因此返回 -1。 

输入样例 复制

4
3 27
8 2 4
4 45
30 0 4 11
1 0
100
6 2
5 5 1 5 1 0

输出样例 复制

Case #1: 12
Case #2: 14
Case #3: 100
Case #4: -1