Codeforces Round 635 (Div. 1) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

binary search

greedy

math

sortings

two pointers

*1700

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. Xenia and Colorful Gems

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputXenia is a girl being born a noble. Due to the inflexibility and harshness of her family, Xenia has to find some ways to amuse herself.

Recently Xenia has bought $$$n_r$$$ red gems, $$$n_g$$$ green gems and $$$n_b$$$ blue gems. Each of the gems has a weight.

Now, she is going to pick three gems.

Xenia loves colorful things, so she will pick exactly one gem of each color.

Xenia loves balance, so she will try to pick gems with little difference in weight.

Specifically, supposing the weights of the picked gems are $$$x$$$, $$$y$$$ and $$$z$$$, Xenia wants to find the minimum value of $$$(x-y)^2+(y-z)^2+(z-x)^2$$$. As her dear friend, can you help her?

Input

The first line contains a single integer $$$t$$$ ($$$1\le t \le 100$$$) — the number of test cases. Then $$$t$$$ test cases follow.

The first line of each test case contains three integers $$$n_r,n_g,n_b$$$ ($$$1\le n_r,n_g,n_b\le 10^5$$$) — the number of red gems, green gems and blue gems respectively.

The second line of each test case contains $$$n_r$$$ integers $$$r_1,r_2,\ldots,r_{n_r}$$$ ($$$1\le r_i \le 10^9$$$) — $$$r_i$$$ is the weight of the $$$i$$$-th red gem.

The third line of each test case contains $$$n_g$$$ integers $$$g_1,g_2,\ldots,g_{n_g}$$$ ($$$1\le g_i \le 10^9$$$) — $$$g_i$$$ is the weight of the $$$i$$$-th green gem.

The fourth line of each test case contains $$$n_b$$$ integers $$$b_1,b_2,\ldots,b_{n_b}$$$ ($$$1\le b_i \le 10^9$$$) — $$$b_i$$$ is the weight of the $$$i$$$-th blue gem.

It is guaranteed that $$$\sum n_r \le 10^5$$$, $$$\sum n_g \le 10^5$$$, $$$\sum n_b \le 10^5$$$ (the sum for all test cases).

Output

For each test case, print a line contains one integer — the minimum value which Xenia wants to find.

Example

Input

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

Output

14 1999999996000000002 24 24 14

Note

In the first test case, Xenia has the following gems:

If she picks the red gem with weight $$$7$$$, the green gem with weight $$$6$$$, and the blue gem with weight $$$4$$$, she will achieve the most balanced selection with $$$(x-y)^2+(y-z)^2+(z-x)^2=(7-6)^2+(6-4)^2+(4-7)^2=14$$$.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/05/2023 06:15:49 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|