TSUM - Triple Sums

You're given a sequence s of N distinct integers.
Consider all the possible sums of three integers from the sequence at three different indices.
For each obtainable sum output the number of different triples of indices 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
-1
2
3
0
5
Output: 1 : 1
2 : 1
4 : 2
5 : 1
6 : 1
7 : 2
8 : 1
10 : 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.


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

hide comments
2021-03-04 05:07:52
Nice problem. Try to create your own Complex struct instead of using complex<long double> to avoid TLE.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.