DWITE, January 2012, Problem 5

Comets have recently passed through your region of space, leaving behind a trail of dust. You would like to get a rough idea of the extent of this pollution, by finding the two most distant dust particles. Here, we define distance as the sum of differences between the $x$, $y$, and $z$ coordinates. For example, the distance between two particles at $(1,4,9)$ and $(4,4,4)$ is $3+0+5=8$.

There are $N$ comets, and we describe each comet with $11$ numbers: $(A,B,C)$, $(D,E,F)$, $(G,H,I)$, and $(U,V)$. A comet's position at time $t$ is given by $(A{t}^2+Bt+C,D{t}^2+Et+F,G{t}^2+Ht+I)$. A comet leaves behind a particle of dust at every integer time $t$ between $U$ and $V$, inclusive.

For example, consider a comet described by $(1,0,0)$, $(0,-2,1)$, $(0,0,6)$, and $(1,5)$. It leaves behind 5 dust particles, at $(1,-1,6)$, $(4,-3,6)$, $(9,-5,6)$, $(16,-7,6)$, and $(25,-9,6)$. The first and last points are the most distant pair, with distance $24+8+0=32$.

Pay close attention to the bounds. You may assume that there will be fewer than $100000$ dust particles, and that all positions will fit within a signed 32-bit integer.

$1\le N\le 100$

$-500\le A,D,G,U,V\le 500$

$-100000\le B,C,E,F,H,I\le 100000$

$U\le V$

The input will contain 5 test cases. Each will begin with a single integer $N$. $N$ lines will follow, each containing $11$ integers, in the order described above.

The output will contain 5 lines of output, one integer for each test case: the distance between the most distant pair of dust particles. There will be at least 2 dust particles.

Sample Input

1
1 0 0 0 -2 1 0 0 6 1 5
3
3 1 4 1 5 9 2 6 5 3 58
2 7 1 8 2 8 1 8 2 8 45
1 6 1 8 0 3 3 9 8 8 74

Sample Output

32
66726

Problem Resource: DWITE