Unless you have been living under a rock, you are surely aware that Josip, Marin, and Paula will represent Croatia at the ICPC World Finals in Russia in 2020/2021. Interestingly, their preparations for the competition are somewhat unconventional. Instead of solving old finals, they persistently come up with new, original problems and participate in organizing high school competitions. Among other things, they are members of the scientific committee for this year's Selection Preparations.

Seeing the results of the first day, they decided to completely change the problemset originally intended for the second day. They worked on the problems all day and all night, finally finishing around four in the morning. They concluded that it was not worth sleeping, so they decided to wait for the start of the competition together in a local bar where they could sip whiskey and Coca-Cola at a round table.

Marin: Look, there is a betting machine in this bar. Shall we play a ticket?

Josip: No one normal is even awake on a Sunday at 4:20 AM, let alone playing some professional sports league.

Paula: I don't know what you're talking about, I just see some doggies running in circles.

And so, our finalists decided to bet on a dog race. $N$ dogs participate in the race, marked with natural numbers from $1$ to $N$. Each of our finalists bet on the exact order of the dogs, meaning their ticket contains a permutation of numbers from $1$ to $N$ which they believe will correspond to the final order of the dogs.

Ready, set, go!

The finalists clutched their tickets tightly until the last dog crossed the finish line. Then, a permutation of numbers from $1$ to $N$ corresponding to the final order appeared on the display. Better luck next time...

Marin: Let me see your tickets, I'm interested in the number of pairs of dogs for which all three of us guessed the relative order correctly or all three of us guessed it incorrectly.

Josip: Hmm, sounds like a good problem, maybe we should put that instead of repeating the one with XORs.

Paula: We have just enough time, but this time I'm making the examples!

Everything is clear to you; determine the number of pairs of dogs $(a, b)$ such that in the final order, dog $a$ arrived at the finish line before dog $b$, and on every ticket, dog $a$ is placed before dog $b$, or on every ticket, dog $b$ is placed before dog $a$.

Input

The first line contains a natural number $N$, the number of dogs.

The second line contains a permutation of numbers from $1$ to $N$ representing the final order of the dogs in the race (from first to last).

The third line contains a permutation of numbers from $1$ to $N$ representing Josip's bet (from the first dog to the last).

The fourth line contains a permutation of numbers from $1$ to $N$ representing Marin's bet (from the first dog to the last).

The fifth line contains a permutation of numbers from $1$ to $N$ representing Paula's bet (from the first dog to the last).

Output

In a single line, print the requested number of pairs of dogs from the problem description.

Subtasks

Examples

Input 1

3
2 3 1
1 2 3
1 2 3
2 3 1

Output 1

1

Input 2

4
3 1 2 4
4 3 2 1
1 2 3 4
1 2 4 3

Output 2

0

Input 3

5
1 3 2 4 5
4 3 5 2 1
4 3 1 2 5
1 2 4 3 5

Output 3

3

Note

Explanation of the third example: All three correctly guessed that dog $3$ would arrive at the finish line before dog $5$, and that dog $4$ would arrive at the finish line before dog $5$. Also, all three incorrectly estimated that dog $4$ would arrive at the finish line before dog $3$.