RT。

样例过不去。我知道还应该处理重复的 $mid$ 值，但样例不需要处理应该也能过。

#include <bits/stdc++.h>
 
using namespace std;

namespace liuzimingc {
#define endl '\n'
#define int long long
const int N = 3e6 + 5, MOD = 1e9 + 7, inv2 = 500000004;

int n, m, a[N], nxt[N][2], siz[N], tot = 1, sum, ans, cnt[N][31];

void insert(int x) {
	int now = 1;
	for (int i = 30; ~i; i--) {
		int p = x >> i & 1;
		if (!nxt[now][p]) nxt[now][p] = ++tot;
		now = nxt[now][p];
		siz[now]++;
	}
}

int ask(int x, int mid) {
	int now = 1, res = 0;
	sum = 0;
	for (int i = 30; ~i; i--) {
		int p = x >> i & 1;
		if (!(mid >> i & 1)) res += siz[nxt[now][p ^ 1]], now = nxt[now][p];
		else now = nxt[now][p ^ 1];
	}
	res += siz[now];
	return res;
}

bool check(int mid) {
	int ans = 0;
	for (int i = 1; i <= n; i++) ans += ask(a[i], mid);
	return ans >= m;
}

void build(int x, int dep, int num) { // the number it represents
	if (!x) return;
	if (dep == -1) {
		for (int i = 0; i <= 30; i++)
			if (num >> i & 1) cnt[x][i] = siz[x];
		return;
	}
	build(nxt[x][0], dep - 1, num);
	build(nxt[x][1], dep - 1, num | (1 << dep));
	for (int i = 0; i <= 30; i++)
		cnt[x][i] = cnt[nxt[x][0]][i] + cnt[nxt[x][1]][i];
}

int get(int x, int mid) {
	int now = 1, ans = 0;
	for (int i = 30; ~i; i--) {
		int p = x >> i & 1;
		if (!(mid >> i & 1)) {
			// 统计 1，跳到 0
			for (int j = 0; j <= 30; j++)
				if (a[i] >> j & 1) ans += (siz[nxt[now][p ^ 1]] - cnt[nxt[now][p ^ 1]][j]) << j;
				else ans += cnt[nxt[now][p ^ 1]][j] << j;
			now = nxt[now][p];
		}
		else now = nxt[now][p ^ 1];
	}
	ans += siz[now] * mid;
	return ans;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> a[i], insert(a[i]);
	m <<= 1;
	int l = 0, r = 2e9;
	while (l < r) {
		int mid = l + r + 1 >> 1;
		if (check(mid)) l = mid;
		else r = mid - 1;
	}
	cout << l << endl;
	build(1, 30, 0);
	for (int i = 1; i <= n; i++) ans += get(a[i], l), cout << i << " " << ans << endl;
	cout << ans << endl;
	cout << ans * inv2 % MOD << endl; // 处理重复情况
	return 0;
	
}
#undef int
} // namespace liuzimingc
    
int main() {
	liuzimingc::main();
	return 0;
}