[hdu 3949] XOR

求去重后异或空间的第K小. T组数据, 每组N个数, Q个询问. (T≤30, 1≤N, Q≤10^4, 其他数是[1,10^18]内的整数) Gauss-Jordan消元, 消出的所有非0数是一组线性基. 设有n个线性基, 则异或空间包含2^n或2n-1个元素, 取决于是否含0. 如果包含0, 则将K减1, 使第1小的元素为正.

考虑是否异或上最大的那个线性基. 如果异或上, 那么得到的是第2^(n-1)~2n-1小, 否则, 得到第0~2^(n-1)-1小. 因为最高位的1仅存在于这一个线性基中. 然后去掉最大的线性基, 递归地二分下去. 注意到这个过程和K的二进制拆分是一致的.

typedef long long ll;
const int N = 1e4;
ll v[N];
int now;

void gauss_jordan(int n)
{
	now = 0;
	for (ll x = 1LL<<59; x && now < n; x >>= 1) {
		int r = now;
		while (r < n && !(v[r] & x)) ++r;
		if (r == n) continue;
		swap(v[r], v[now]);
		Rep (i, 0, n) if (i != now && (v[i] & x)) v[i] ^= v[now];
		++now;
	}
}

ll solve(int n, ll k)
{
	k -= now < n;
	if (k == 0) return 0;
	if (k >= (1LL<<now)) return -1;
	ll ans = 0, x = 1LL<<(now-1);
	Rep (i, 0, now) {
		if (k & x)
			ans ^= v[i];
		x >>= 1;
	}
	return ans;
}

int main()
{
	int T;
	scanf("%d", &T);
	For (t, 1, T) {
		printf("Case #%d:\n", t);
		int n;
		scanf("%d", &n);
		Rep (i, 0, n)
			scanf("%lld", &v[i]);
		gauss_jordan(n);
		int q;
		scanf("%d", &q);
		while (q--) {
			ll k;
			scanf("%lld", &k);
			printf("%lld\n", solve(n, k));
		}
	}
	return 0;
}