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

(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```

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <map>
#include <list>

using namespace std;

int a[4001],b[4001],c[4001],d[4001];
int A[16000002];
int B[16000002];

int main(){
int n;
long long sum=0;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);
}
long t1=0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
A[t1++]=a[i]+b[j];
}
}
t1=0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
B[t1++]=-c[i]-d[j];
}
}
sort(A,A+t1);
sort(B,B+t1);

for(long i=0;i<t1;){
long size1=0;
int no=A[i];
while(A[i]==no<t1){
size1++;
i++;
}
long low=0;
long high=t1;
long mid;
long temp=0;
long size=0;
while(low<=high){
mid=(low+high)/2;
if(B[mid]==no){
temp=mid-1;
while(mid<t1&&B[mid]==no){
size++;
mid++;
}
while(temp>=0&&B[temp]==no){
size++;
temp--;
}
break;
}
else if(B[mid]<no){
low=mid+1;
}
else if(B[mid]>no){
high=mid-1;
}
}
sum+=size1*size;
}
printf("%lld\n",sum);
return 0;
}``````
Copy The Code &

Input

cmd
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

cmd
5

### #2 Code Example with Java Programming

```Code - Java Programming```

``````#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int const N = 2501;
int n, a[N], b[N], c[N], d[N];
vector<int> all;

int main() {
scanf("%d", &n);
for(int i = 0; i < n; ++i)
scanf("%d %d %d %d", a + i, b + i, c + i, d + i);

for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j)
all.push_back(a[i] + b[j]);

sort(all.begin(), all.end());

pair<vector<int>::iterator, vector<int>::iterator> bounds;
int res = 0;
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j) {
int tmp = -(c[i] + d[j]);
bounds = equal_range(all.begin(), all.end(), tmp);
res += bounds.second - bounds.first;
}

printf("%d\n", res);

return 0;
}``````
Copy The Code &

Input

cmd
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

cmd
5