Snuke Festival

Source: AtCoder

Version: Phuoc Hung OJ Extended

Problem Statement

An altar consists of exactly one upper part, one middle part, and one lower part. There are $N$ parts in each category, with sizes $A_1,\ldots,A_N$, $B_1,\ldots,B_N$, and $C_1,\ldots,C_N$.

A triple of indices $(i,j,k)$ is valid exactly when

Two altars are different if at least one selected part is different. Thus equal-sized parts with different indices are still distinct choices.

Count the number of valid triples.

Input

• The first line contains $N$.
• The second line contains $A_1,\ldots,A_N$.
• The third line contains $B_1,\ldots,B_N$.
• The fourth line contains $C_1,\ldots,C_N$.

Output

Print the number of valid altars.

Subtasks

• Subtask 1 — 20%: $1\le N\le50$.
• Subtask 2 — 30%: $1\le N\le3000$.
• Subtask 3 — 50%: $1\le N\le10^5$, $1\le A_i,B_i,C_i\le10^9$.

Example

Input

2
1 5
2 4
3 6

Output

3

Explanation

The three valid choices are $(A_1,B_1,C_1)$, $(A_1,B_1,C_2)$, and $(A_1,B_2,C_2)$.