评测记录

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define PLL pair<LL, LL>

const int N = 1e6 + 10;
namespace IO
{
	char buf[1 << 21], *p1 = buf, *p2 = buf;
	inline char gc()
	{
	    #ifdef LOCAL 
	    return getchar();
	    #endif 
	    if(p1 == p2) p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin);
	    return p1 == p2 ? EOF : *p1++;
	}
	template<typename T = int>
	inline T read()
	{
	    int f = 1;
	    T w = 0;
	    char ch = gc();
	    while(ch < '0' || '9' < ch)
	    {
	        if(ch == '-') f = -1;
	        ch = gc();
	    }
	    while('0' <= ch && ch <= '9')
	    {
	        w = (w << 1) + (w << 3) + (ch ^ 48);
	        ch = gc();
	    }
	    return f * w;
	}
	inline char readc()
	{
	    char ch = gc();
	    while(ch == ' ' || ch == '\n') ch = gc();
	    return ch;
	}
	char obuf[1 << 21], *p3 = obuf;
	inline void flush()
	{
		fwrite(obuf, p3 - obuf, 1, stdout);
	}
	inline void pc(char c)
	{
	    p3 - obuf <= 1 << 20 ? *p3++ = c : (flush(), p3 = obuf, *p3++ = c);
	}
	template<typename T>
	inline void write(T x)
	{
	    if(x < 0) pc('-'), x = -x;
	    if(x == 0) pc('0');
	    static char c[50];
	    static int tt;
	    while(x) c[++tt] = x % 10 ^ 48, x /= 10;
	    while(tt) pc(c[tt--]);
	}
}
using namespace IO;
int n;
LL a[N];
vector<LL> s[4], ss[2];

void solve()
{
	LL val1, val2;
	if(!s[0].empty() && !s[2].empty())
	{
		val1 = s[0].back(), s[0].pop_back();
		val2 = s[2].back(), s[2].pop_back();
	}
	else
	{
		val1 = s[1].back(), s[1].pop_back();
		val2 = s[3].back(), s[3].pop_back();
	}
	ss[0] = s[0], ss[1] = s[1];
	for(LL i : s[2]) ss[0].push_back(i);
	for(LL i : s[3]) ss[1].push_back(i);
	while(ss[0].size() >= 2 || ss[1].size() >= 2)
		for(int j = 0; j <= 1; j++)
			if(ss[j].size() >= 2)
			{
				vector<LL> t = ss[j];
				ss[j].clear();
				for(int i = 0; i < t.size(); i += 2)
					if(i + 1 < t.size()) 
					{
						write(t[i]), pc(' '), write(t[i + 1]), pc('\n');
						ss[(t[i] + t[i + 1]) / 2 % 2].push_back((t[i] + t[i + 1]) / 2);
					}
					else ss[t[i] % 2].push_back(t[i]);
			}
	ss[val1 & 1].push_back(val1), ss[val2 & 1].push_back(val2);
}

vector<PLL> ans;
bool dfs(vector<LL> &s0, vector<LL> &s1)
{
	if(s0.size() + s1.size() == 1) 
	{
		for(PLL i : ans) write(i.first), pc(' '), write(i.second), pc('\n');
		return true;
	}
	for(int i = 0; i < s0.size(); i++)
		for(int j = i + 1; j < s0.size(); j++)
		{
			vector<LL> t0, t1 = s1;
			for(int k = 0; k < s0.size(); k++)
				if(k != i && k != j) t0.push_back(s0[k]);
			ans.push_back({s0[i], s0[j]});
			if((s0[i] + s0[j]) / 2 & 1) t1.push_back((s0[i] + s0[j]) / 2);
			else t0.push_back((s0[i] + s0[j]) / 2);
			if(dfs(t0, t1)) return true;
			ans.pop_back();
		}
	for(int i = 0; i < s1.size(); i++)
		for(int j = i + 1; j < s1.size(); j++)
		{
			vector<LL> t0 = s0, t1;
			for(int k = 0; k < s1.size(); k++)
				if(k != i && k != j) t1.push_back(s1[k]);
			ans.push_back({s1[i], s1[j]});
			if((s1[i] + s1[j]) / 2 & 1) t1.push_back((s1[i] + s1[j]) / 2);
			else t0.push_back((s1[i] + s1[j]) / 2);
			if(dfs(t0, t1)) return true;
			ans.pop_back();
		}
	return false;
}

int main()
{
	int T = read();
	while(T--)
	{
		s[0].clear(), s[1].clear(), s[2].clear(), s[3].clear();
		n = read();
		for(int i = 1; i <= n; i++) 
			a[i] = read<LL>(), s[a[i] % 4].push_back(a[i]);
		
		if(!s[0].empty() && !s[2].empty() || !s[1].empty() && !s[3].empty())
		{
			solve(), ans.clear(), dfs(ss[0], ss[1]);
			continue;
		}
		if(s[0].empty() && s[2].empty() || s[1].empty() && s[3].empty())
		{
			while(1)
			{
				bool flag = 0;
				for(int i = 0; i <= 3; i++)
					if(s[i].size() >= 2)
					{
						LL val1 = s[i].back(); s[i].pop_back();
						LL val2 = s[i].back(); s[i].pop_back();
						write(val1), pc(' '), write(val2), pc('\n');
						s[(val1 + val2) / 2 % 4].push_back((val1 + val2) / 2);
						flag = 1;
					}
				if(!flag) break;
			}
			ss[0] = s[0], ss[1] = s[1];
			for(LL i : s[2]) ss[0].push_back(i);
			for(LL i : s[3]) ss[1].push_back(i);
			ans.clear(), dfs(ss[0], ss[1]);
			continue;
		}
	}
	return flush(), 0;
}