Hide

Problem F
Final Exam

In the final round of the Hunter Exam, candidates must prove their ability to process big data as well as geometry knowledge.

In the Examination Hall, the candidates can find three piles of segments:

  • The first pile has $n_ a$ segments, and the $i$-th segment has length $A_ i$.

  • The second pile has $n_ b$ segments, and the $j$-th segment has length $B_ j$.

  • The third pile has $n_ c$ segments, and the $k$-th segment has length $C_ k$.

The candidates must quickly select three segments, one segment from each pile, such that:

  • The three segments can be used to form a right triangle.

  • The segment chosen from the third pile must be longest.

As the organizer of the Hunter Exam, you need to make sure that the difficulty is right for the final round. Thus you want to know the number of ways to select three segments, satisfying the conditions above?

Input

The first line of the input contains exactly three integers: $n_ a$, $n_ b$ and $n_ c$ $(1 \le n_ a, n_ b, n_ c \le 3 \cdot 10^5)$.

The second line of the input contains exactly $n_ a$ integers — the lengths of the segments in the first pile.

The third line of the input contains exactly $n_ b$ integers — the lengths of the segments in the second pile.

The fourth line of the input contains exactly $n_ c$ integers — the lengths of the segments in the third pile.

All the lengths of the segments are between $1$ and $3 \cdot 10^7$, inclusive.

Output

Print exactly one integer — the number of triplets.

Explanation of sample test

There are $4$ different ways to select three segments: $(3, 4, 5)$, $(3, 4, 5)$, $(4, 3, 5)$ and $(4, 3, 5)$.

Selecting $(5, 4, 3)$ is not valid, as the segment from the third pile must be the longest segment.

Sample Input 1 Sample Output 1
3 2 3
3 4 5
4 3
5 5 3
4

Please log in to submit a solution to this problem

Log in