SUMFOUR - 4 values whose sum is 0

no tags 

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, we 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 .

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 Pentium G860 3GHz)
Languages:All except: ERL JS NODEJS PERL 6 SCM chicken VB.net
Resource:South western 05-06

hide comments
Lehar: 2015-04-12 17:51:25

Damn! Finally AC! :D

lucky: 2015-03-29 10:56:43

O(n^2 *logn) is giving me a TLE why????? is der any better method

Last edit: 2015-03-29 10:57:10
Noureldin Yosri: 2015-03-11 20:51:09

O(n^2 log(n)) + optimization
caution : std::map is very slow

Kishlay Raj: 2015-02-01 09:42:35

3
0 0 0 0
0 0 0 0
-1 -1 1 1

Rajat (1307086): 2015-01-31 01:42:23

Lot of optimization needed.

kailash: 2015-01-20 07:35:33

@Chandan Mittal if you have used cin and cout , try using printf and scanf

Chandan Mittal: 2015-01-08 23:56:49

O(n^2 * log(n)) gives TLE. But why??? :(

ankit kumar sinha: 2015-01-01 14:14:07

dont use long long int. gives TLE

ashish kumar: 2014-12-29 13:55:20

wrong ans on test case 9

Miguel Oliveira: 2014-06-11 13:51:00

very weak test cases, it doesn't even have n up to 4000