來水題解了喵。這題有紫？

首先合理猜測最終的操作一定是先 \(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\) 的數先操作，若不夠操作數則繼續向 \(1\) 操作。

考慮如何維護這個東西。很顯然的想到 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 樹上維護子樹中數的個數、子樹中數的和與子樹中數的按位與即可（注意一個細節是，當遍歷到的點只有 \(0\) 兒子或者 \(1\) 兒子，直接遞歸即可，否則樣例第三組數據可能輸出 \(0\)），很簡單很好寫喵。時間復雜度為 \(\mathcal{O}(n \log a_i)\)（處理出 Trie 樹），遞歸求解是 \(\mathcal{O}(\log a_i)\) 的。

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;
}