Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Difference between Triplets
Time Limit: 3000MSMemory Limit: 65536K
Total Submissions: 3271Accepted: 1128

Description

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, JaJb, KaKb} − min {Ia Ib, JaJb, KaKb}

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?

Input

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.

Output

For each case, output a line with the sum of difference values between every unordered pair of triplets.

Sample Input

2
1 2 3
3 2 1
3
1 3 2
4 0 7
2 2 9
0

Sample Output

4
20

Hint

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 [-106,106].
The size of the input will not exceed 5 MB.

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator