## TSUM - Triple Sums

no tags

You're given a sequence s of N distinct integers.
Consider all the possible sums of three integers from the sequence at three different indicies.
For each obtainable sum output the number of different triples of indicies that generate it.

Constraints:

N <= 40000, |si| <= 20000

### Input

The first line of input contains a single integer N.
Each of the next N lines contain an element of s.

### Output

Print the solution for each possible sum in the following format:
sum_value : number_of_triples

Smaller sum values should be printed first.

### Example

```Input:5-12305Output:
1 : 12 : 14 : 25 : 16 : 17 : 28 : 110 : 1```

Explanation:
4 can be obtained using triples ( 0, 1, 2 ) and ( 0, 3, 4 ).
7 can be obtained using triples ( 0, 2, 4 ) and ( 1, 3, 4 ).

Note: a triple is considered the same as any of its permutations.

hide comments

 Added by: gustav Date: 2011-02-18 Time limit: 0.471s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: ASM64 Resource: own problem, used for a contest on codechef