可以来拯救吗

题号：NC15738
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld

题目描述

quailty is BNU's red sun.

quailty非常喜欢给同学讲题，一天，他又拉着SK给他讲题。

quailty：给一个长为n的序列，求给定子序列的和，会吗？

SK：。。

quailty：给一个长为n的序列，求给定子序列的和的平方，会吗？

SK：。。。

quailty：给一个长为n的序列，求所有子序列的和的平方和，会吗？

SK：。。。。。

quailty：给一个长为n的序列，求所有长为k的子序列的和的平方和，会吗？

SK：。。。。。。。。

quailty：给一个长为n的序列，求所有长为k的子序列的和的平方的异或和，会...

SK：我^(^&*((^%^#……

SK拔出了他的40m长刀，场面就快控制不住了，请你赶快来做出这道题，拯救一下quailty。

quailty is BNU's red sun.

输入描述:

第一行是一个正整数T(≤ 10)，表示测试数据的组数，

对于每组测试数据，

第一行是两个正整数n,k(k ≤ n ≤ 100000)，分别表示序列长度和需要考虑的子序列长度，

接下来一行包含n个不超过1000的正整数，表示序列的n个元素 $a_1,a_2,\dots,a_n$ ，

为了简化问题，保证 $C_{n}^{k} \leq 100000$ ，也就是说，需要考虑的子序列不超过100000个。

输出描述:

对于每组测试数据，输出一行，包含一个整数，表示所有长为k的子序列的和的平方的异或和。

示例1

输入

复制

1
4 2
1 2 3 4

输出

复制

说明

对于样例，长度为2的子序列有[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]，所以答案是9^16^25^25^36^49=12（这里'^'是C++中的异或运算符）。