← 返回题目列表

Codeforces · 1336/B

B. 齐妮娅和七彩宝石

中文机器翻译题面 查看原题

仙妮亚是一个出身贵族的女孩。由于家庭的不灵活和严厉,Xenia 必须找到一些方法来娱乐自己。

最近 Xenia 购买了 $$$n_r$$$ 红色宝石、$$$n_g$$$ 绿色宝石和 $$$n_b$$$ 蓝色宝石。每颗宝石都有重量。

现在,她要挑选三颗宝石。

Xenia 喜欢色彩缤纷的东西,所以她会每种颜色恰好挑选一颗宝石。

Xenia喜欢平衡,所以她会尽量挑选重量相差不大的宝石。

具体来说,假设拾取的宝石的重量为$$$x$$$、$$$y$$$和$$$z$$$,Xenia想要找到$$$(x-y)^2+(y-z)^2+(z-x)^2$$$的最小值。作为她亲爱的朋友,你能帮助她吗?

输入

第一行包含一个整数 $$$t$$$ ($$$1\le t \le 100$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。

每个测试用例的第一行包含三个整数 $$$n_r,n_g,n_b$$$ ($$$1\le n_r,n_g,n_b\le 10^5$$$) — 分别是红色宝石、绿色宝石和蓝色宝石的数量。

每个测试用例的第二行包含 $$$n_r$$$ 整数 $$$r_1,r_2,\ldots,r_{n_r}$$$ ($$$1\le r_i \le 10^9$$$)  — $$$r_i$$$ 是第 $$$i$$$ 红色宝石的重量。

每个测试用例的第三行包含 $$$n_g$$$ 整数 $$$g_1,g_2,\ldots,g_{n_g}$$$ ($$$1\le g_i \le 10^9$$$)  — $$$g_i$$$ 是第 $$$i$$$ 绿色宝石的重量。

每个测试用例的第四行包含 $$$n_b$$$ 整数 $$$b_1,b_2,\ldots,b_{n_b}$$$ ($$$1\le b_i \le 10^9$$$) — $$$b_i$$$ 是第 $$$i$$$ 蓝色宝石的重量。

保证 $$$\sum n_r \le 10^5$$$、$$$\sum n_g \le 10^5$$$、$$$\sum n_b \le 10^5$$$ (所有测试用例的总和)。

输出

对于每个测试用例,打印一行包含一个整数 - Xenia 想要找到的最小值。

示例

输入 #1

5
2 2 3
7 8
6 3
3 1 4
1 1 1
1
1
1000000000
2 2 2
1 2
5 4
6 7
2 2 2
1 2
3 4
6 7
3 4 1
3 2 1
7 3 3 4
6

输出 #1

14
1999999996000000002
24
24
14

注意

在第一个测试用例中,Xenia 拥有以下宝石:

如果她选择重量为 $$$7$$$ 的红色宝石、重量为 $$$6$$$ 的绿色宝石和重量为 $$$4$$$ 的蓝色宝石,她将实现最平衡的选择$$$(x-y)^2+(y-z)^2+(z-x)^2=(7-6)^2+(6-4)^2+(4-7)^2=14$$$。