描述：

你可能好奇为什么大多数外星生命形态都类似人类，仅通过一些表面特征来区分，比如身高、肤色、皱纹、耳朵或眉毛等。少数生命体与人类毫无相似之处，它们通常具有几何或非晶态形状，如立方体、油膜或尘埃云。

答案在《星际迷航：下一代》第$146$集《追逐》中揭晓。研究发现，该象限中绝大多数生命形式的DNA中存在大量相同的片段。

给定多个生命体的DNA序列（由小写字母组成的字符串），请找出被超过半数生命体共享的最长子串。

输入
标准输入包含多个测试用例。每个测试用例以$1 \leq n \leq 100$（生命体数量）开始。随后是$n$行，每行一个由小写字母组成的字符串，表示一个生命体的DNA序列。每个DNA序列长度在$1$到$1000$之间。最后一个测试用例后跟一行$0$。

输出
对于每个测试用例，输出被超过半数生命体共享的最长子串（可能有多个）。若存在多个，按字母序输出所有结果；若无符合要求的解（长度至少为$1$），输出?。测试用例之间需空一行。

关键点说明：

1. 数学标记：如$1 \leq n \leq 100$、$146$等数字和公式已按需添加符号。
2. 术语统一：
   • "life forms" 译为“生命体”而非“生命形式”，更简洁。
   • "more than half" 译为“超过半数”，符合中文比例表达习惯。
3. 格式保留：
   • 输入输出要求中的代码符号（如?）保留原格式。
   • 测试用例间的空行要求明确标注。
4. 文化适配：
   • 剧集标题《The Chase》采用官方译名《追逐》，避免直译歧义。

代码实现

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long ll;
const int MAX_N = 100020;

struct P
{
	int x;
	int y;
	bool operator< (const P& ri)const
	{
		return x < ri.x || x == ri.x && y < ri.y;
	}
};
P p[MAX_N];
int kx[MAX_N];
int ky[MAX_N];

bool E[MAX_N];

int bit[MAX_N], _n;
void add(int i, const int x);
int sum(int i);

ll solve();

int main()
{
	int T;
	scanf("%d", &T);
	
	while (T--)
	{
		printf("%lld\n", solve());
	}
	return 0;
}

void add(int i, const int x)
{
	i += 2;
	while (i < _n)
	{
		bit[i] += x;
		i += i & -i;
	}
}

int sum(int i)
{
	i += 2;
	int s = 0;
	while (i)
	{
		s += bit[i];
		i -= i & -i;
	}
	return s;
}

ll solve()
{
	static const int Invalid = -1;
	int n;
	scanf("%d", &n);
	
	int kxcnt = 0, kycnt = 0;
	for (int i = 0; i < n; ++i)
	{
		P& cur = p[i];
		scanf("%d%d", &cur.x, &cur.y);
		kx[kxcnt++] = cur.x;
		ky[kycnt++] = cur.y;
	}
	sort(p, p + n);
	sort(kx, kx + kxcnt);
	sort(ky, ky + kycnt);
	kxcnt = unique(kx, kx + kxcnt) - kx;
	kycnt = unique(ky, ky + kycnt) - ky;
	for (int i = 0; i < n; ++i)
	{
		P& cur = p[i];
		cur.x = lower_bound(kx, kx + kxcnt, cur.x) - kx;
		cur.y = lower_bound(ky, ky + kycnt, cur.y) - ky;
	}
	p[n].x = p[n].y = -1;
	
	_n = n + 4;
	memset(bit, 0, _n * sizeof(bit[0]));
	memset(E, 0, (n + 1) * sizeof(E[0]));
	
	ll res = 0;
	int lb = 0, rb = 0, ecnt = 0;
	for (int i = 0; i < kxcnt; ++i)
	{
		while (p[rb].x == i) ++rb;
		if ((rb - lb) & 1) return Invalid;
		
		if (i) res += (ll)ecnt * (kx[i] - kx[i - 1]);
		
		while (lb != rb)
		{
			const P& lo = p[lb++];
			const P& up = p[lb++];
			if (lo.y == up.y) return Invalid;
			
			int t1 = sum(lo.y);
			int t2 = sum(up.y - 1);
			if (t1 != t2) return Invalid;
			
			add(lo.y, E[lo.y] ? -1 : 1);
			add(up.y, E[up.y] ? -1 : 1);
			
			res += ky[up.y] - ky[lo.y];
			if (E[lo.y]) --ecnt;
			else ++ecnt;
			if (E[up.y]) --ecnt;
			else ++ecnt;
			
			E[lo.y] = !E[lo.y];
			E[up.y] = !E[up.y];
		}
		if (i + 1 < kxcnt && !ecnt) return Invalid;
	}
	
	for (int i = 0; i <= kycnt; ++i)
	{
		if (sum(i)) return Invalid;
	}
	return res;
}