来水题解了喵。这题有紫？
首先合理猜测最终的操作一定是先 \(n-k\) 次 \(1\) 操作后若干次 \(2\) 操作，不妨认为这是对的考虑怎么证明一下。转化一下，我们要证的就是：\((x \otimes y) + z \geq (x + y) \otimes z\)（话说为什么按位与符号是这个，好奇怪喵）。容易发现 \((x + y) \otimes z \leq z\)，而 \((x \otimes y) + z \geq z\)。
接着我们考虑贪心的进行前 \(n-k\) 次 \(1\) 操作。我们发现 \(a \otimes b = a + b - a | b\) 其中 \(|\) 为按位或操作。假设我们每步操作的两个数的按位或之和为 \(b\)，那么我们最终的答案即为 \(\sum a_i - b\)，也就是说我们要最小化 \(b\)。
于是我们发现：对于二进制下从低到高第 \(i\) 位为 \(0\) 的数和第 \(i\) 位为 \(1\) 的数（不妨假设更高位均相同），优先选择第 \(i\) 位为 \(0\) 的数进行操作是更优的（因为前者操作后的产生的按位或第 \(i\) 位为 \(0\) 而后者为 \(1\)）。于是我们有了一个贪心策略：从大到小枚举 \(2^i\)，优先将这一位为 \(0\) 的数先操作。
考虑如何维护这个东西。很显然的想到 01-Trie，建出树后从根开始向下遍历保证枚举的 \(2^i\) 从大到小。若这一位为 \(0\) 的数足够 \(k\) 次操作，就向 \(0\) 儿子继续遍历；否则需要对 \(1\) 儿子进行操作。设 \(0\) 儿子子树中所有数的按位与结果为 \(x\)，那么我们要将这个数添加到我们进行操作的序列中去。如果每次记录这样的 \(x\) 未免太过麻烦，我们令 \(x\) 的第 \(i\) 位为 \(1\) 将其加入 Trie 树中，这样就可以优雅的继续向 \(1\) 儿子递归，统计答案时减去 \(2^i\) 即可。
考虑如何获得答案。在递归过程中，如果递归到叶子节点且还剩余 \(k\) 次操作与 \(m\) 个数，那么答案就加上 \((m - k) \times val\)（\(val\) 为当前遍历到的数）；若向 \(0\) 儿子遍历，那么就可以取遍 \(1\) 儿子子树中的和加入答案。可以感性理解一下这为什么是对的。
回顾整道题，我们只需要在 Trie 树上维护子树中数的个数、子树中数的和与子树中数的按位与即可，代码很简单。
const int N=1e6+5,S=2e7+5;
int T,n,k,a[N];
int tr[S][2],siz[S],nd[S],cnt;
ll ans,sum[S];inline int new_node() {++cnt,siz[cnt]=0,nd[cnt]=(1<<30)-1;sum[cnt]=tr[cnt][0]=tr[cnt][1]=0;return cnt;
}
inline void insert(int x) {int p=0; siz[0]++;for(int j=29;j>=0;j--) {int dir=(x>>j)&1;if(!tr[p][dir]) tr[p][dir]=new_node();siz[p=tr[p][dir]]++,nd[p]&=x,sum[p]+=x;}return ;
}
#define lc tr[p][0]
#define rc tr[p][1]
inline void solve(int p,int k,int bit,int num) {// printf("solve(%d,%d,%d,%d): %lld\n",p,k,bit,num,ans);if(!bit) {ans+=(ll)num*(siz[p]-k);// printf("%d %d %d %lld\n",num,siz[p],k,ans);return ;}if(!lc) return solve(rc,k,bit-1,num|(1<<bit-1));if(!rc) return solve(lc,k,bit-1,num);if(lc&&siz[lc]>k) {ans+=sum[rc];solve(lc,k,bit-1,num);}else {if(lc) insert(nd[lc]|(1<<bit-1));solve(rc,k-(lc?siz[lc]-1:0),bit-1,num|(1<<bit-1));ans-=(1<<bit-1);}return ;
}int main() {read(T);while(T--) {read(n,k),k=n-k,cnt=tr[0][0]=tr[0][1]=0;for(int i=1;i<=n;i++) read(a[i]),insert(a[i]);ans=0,solve(0,k,30,0);write(ans),_E;}return 0;
}