SUMFOUR - 4 values whose sum is 0

The SUM problem can be formulated as follows: given four lists A, B, C, D of integer values, compute how many quadruplet (a, b, c, d ) belongs to A x B x C x D are such that a + b + c + d = 0. In the following, assume that all lists have the same size n.

Input

The first line of the input file contains the size of the lists n (this value can be as large as 4000). We then have n lines containing four integer values (with absolute value as large as 228 ) that belong respectively to A, B, C and D.

(Edited: n <= 2500)

Output

Output should be printed on a single line.

Example

Input:
6
-45 22 42 -16
-41 -27 56 30
-36 53 -37 77
-36 30 -75 -46
26 -38 -10 62
-32 -54 -6 45

Output:
5

Added by:Abhilash I
Date:2007-02-06
Time limit:1.419s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:South western 05-06

hide comments
2015-06-19 00:31:13 sujit yadav
take 2 pointer array in pair stl ....learn a lot .. thanks !!! :)
2015-06-16 22:13:57
can you tell the tenth case??
it is giving wrong ans :( :(
2015-06-08 20:48:58 xxbloodysantaxx
Time Limit is too strict will make you cry!
2015-06-08 04:53:20 kirakira
damn i almost cry for not AC such "easy" problem :(
Do not use long long, do not use binary search, in my case, I even cannot use STL::vector / map / set, etc.
2015-05-08 15:19:09 i_am_looser
STL - took 5 minute to get AC : )
2015-04-12 17:51:25 Lehar
Damn! Finally AC! :D
2015-03-29 10:56:43 lucky
O(n^2 *logn) is giving me a TLE why????? is der any better method

Last edit: 2015-03-29 10:57:10
2015-03-11 20:51:09 Noureldin Yosri
O(n^2 log(n)) + optimization
caution : std::map is very slow
2015-02-01 09:42:35 Kishlay Raj
3
0 0 0 0
0 0 0 0
-1 -1 1 1
2015-01-31 01:42:23 Rajat (1307086)
Lot of optimization needed.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.