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-01-20 07:35:33 kailash
@Chandan Mittal if you have used cin and cout , try using printf and scanf
2015-01-08 23:56:49 Chandan Mittal
O(n^2 * log(n)) gives TLE. But why??? :(
2015-01-01 14:14:07 ankit kumar sinha
dont use long long int. gives TLE
2014-12-29 13:55:20 ashish kumar
wrong ans on test case 9
2014-06-11 13:51:00 Miguel Oliveira
very weak test cases, it doesn't even have n up to 4000
2010-02-23 11:24:23 Ehor Nechiporenko
Manish - the right answer 4^4 = 256


Last edit: 2010-10-21 05:27:15
2010-02-11 16:11:33 Manish kumar
4
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
whats the answer for this input ? problem looks for distinct quadruplet, right ?
2009-06-30 02:40:46 Ruslan Sennov
hint:
sort() in C++ runs faster than qsort in C
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.