Four Integers Summing to Zero

Interview

Time limit12sMemory limit1024 MB

Summary

Count the number of index tuples (a, b, c, d) with A[a] + B[b] + C[c] + D[d] = 0, given four arrays of size n.

Level: Medium6 of 10
Topics: Hash map, Sorting, Two pointers, Array
Solved: No attempts yet

Problem

You are given four integer arrays $A$ , $B$ , $C$ , and $D$ , all of the same size.

Write a program that counts the number of tuples $(a, b, c, d)$ such that $A[a] + B[b] + C[c] + D[d] = 0$ . Here $a$ , $b$ , $c$ , and $d$ are indices from $0$ to $n-1$ , choosing one element independently from each of the four arrays.

Input

The first line contains the array size $n$ $(1 \le n \le 4000)$ . Each of the next $n$ lines contains the integers belonging to $A$ , $B$ , $C$ , and $D$ , separated by spaces; the four integers on the $i$ -th line are $A[i]$ , $B[i]$ , $C[i]$ , and $D[i]$ in that order. The absolute value of every integer is at most $2^{28}$ .

Output

Print the number of tuples $(a, b, c, d)$ whose sum is $0$ .

Examples4

Example 1

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

Expected output

Example 2
Input
```
1
0 0 0 0
```
Expected output
```
1
```
Example 3
Input
```
1
1 1 1 1
```
Expected output
```
0
```
Example 4
Input
```
2
1 1 1 1
-1 -1 -1 -1
```
Expected output
```
6
```