Three Shifts - Repovive Starter Round 3 | Repovive

12F. Three Shifts

3000 pts2s256 MB

You are given three arrays $a$ , $b$ , and $c$ , each of length $n$ .

You may cyclically shift each array any number of times. More formally, for each array you may choose any rotation of its elements.

After choosing the rotations, let the resulting arrays be $A$ , $B$ , and $C$ .

The score of these three arrays is

\sum_{i=1}^{n} (A_i+B_i+C_i)^2.

Find the maximum possible score.

Constraints

$1 \le t \le 1000$
$1 \le n \le 5000$
The sum of $n$ over all test cases is at most $5000$
$0 \le a_i,b_i,c_i \le 10^6$

Input

t

\left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \\ b_1 \quad b_2 \quad \cdots \quad b_n \\ c_1 \quad c_2 \quad \cdots \quad c_n \end{array} \right\} \times t

Output

\left. \begin{array}{l} ans \end{array} \right\} \times t

Samples

Input

Case 1

Case 2

Case 3

Case 4

Case 5

Explanation

Case 1

There is only one position, so the score is $(1+2+3)^2=36$ .

Case 2

One best choice makes the arrays $[1,10]$ , $[1,10]$ , and $[5,5]$ . The score is $7^2+25^2=674$ .

Case 3

We can rotate the arrays so that all three values $10$ are placed in the same position. The score becomes $30^2=900$ .

Case 4

One best choice makes the third array $[1,0,3,2]$ . The position sums become $[2,2,6,6]$ , so the score is $4+4+36+36=80$ .

Case 5

One best choice makes the second array $[8,1,5,0,2]$ and keeps the third array unchanged. The position sums become $[18,2,16,2,14]$ , so the score is $324+4+256+4+196=784$ .

Output

Case 1

Case 2

Case 3

Case 4

Case 5

You are given three arrays $a$ , $b$ , and $c$ , each of length $n$ .

You may cyclically shift each array any number of times. More formally, for each array you may choose any rotation of its elements.

After choosing the rotations, let the resulting arrays be $A$ , $B$ , and $C$ .

The score of these three arrays is

\sum_{i=1}^{n} (A_i+B_i+C_i)^2.

Find the maximum possible score.

$1 \le t \le 1000$
$1 \le n \le 5000$
The sum of $n$ over all test cases is at most $5000$
$0 \le a_i,b_i,c_i \le 10^6$

t

\left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \\ b_1 \quad b_2 \quad \cdots \quad b_n \\ c_1 \quad c_2 \quad \cdots \quad c_n \end{array} \right\} \times t

\left. \begin{array}{l} ans \end{array} \right\} \times t

There is only one position, so the score is $(1+2+3)^2=36$ .

One best choice makes the arrays $[1,10]$ , $[1,10]$ , and $[5,5]$ . The score is $7^2+25^2=674$ .

We can rotate the arrays so that all three values $10$ are placed in the same position. The score becomes $30^2=900$ .

One best choice makes the third array $[1,0,3,2]$ . The position sums become $[2,2,6,6]$ , so the score is $4+4+36+36=80$ .

One best choice makes the second array $[8,1,5,0,2]$ and keeps the third array unchanged. The position sums become $[18,2,16,2,14]$ , so the score is $324+4+256+4+196=784$ .

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

12F. Three Shifts

Constraints

Input

Output

Samples

12F. Three Shifts

Constraints

Input

Output

Samples