For every pair of triplets, Ta = (Ia, Ja, Ka) and Tb = (Ib, Jb, Kb), we define the difference value between Ta and Tb as follows:
D(Ta, Tb) = max {Ia − Ib, Ja − Jb, Ka − Kb} − min {Ia − Ib, Ja − Jb, Ka − Kb}
Now you are given
N triplets, could you write a program to calculate the sum of the difference values between every unordered pair of triplets?
The input consists of several test cases.
Each test case begins with a line containing an integer
N, denotes the number of triplets. Assume that we number the triplets as
T1,
T2, ... ,
TN. Then, there are following
N lines, each line contains three integers, giving the elements of each triplet.
A case with
N = 0 indicates the end of the input.
For each case, output a line with the sum of difference values between every unordered pair of triplets.
Case 1:
D(
T1,
T2)=4
Case 2:
D(
T1,
T2)+
D(
T1,
T3)+
D(
T2,
T3)=8+8+4=20
You can assume that
N, the number of triplets in each case, will not exceed 200,000 and the elements in triplets fit into [-10
6,10
6].
The size of the input will not exceed 5 MB.