Bajtek came to a casino, where he immediately became interested in a slot machine. The most important part of the machine is its three reels. Each of them is divided into $n$ equal fields, on which different symbols are painted. There are $n$ possible symbols, and each of them appears on each reel exactly once. For simplicity, let us number the symbols with integers from 1 to $n$. The figure below shows an example of a slot machine with three reels divided into $n = 5$ fields:

After pulling the lever, each of the reels shifts cyclically by a certain number of positions. The player's winnings depend on the number of horizontal rows that contain three identical symbols.

Bajtek knows that the slot machine could take all his money, so he would prefer to first determine what his maximum possible winnings could be. Help him and determine the number of rows in which three identical symbols can be found with the most favorable arrangement of the reels.

Input

The first line of input contains a single integer $n$ ($1 \le n \le 300\,000$), representing the size of the reels. The next three lines describe the arrangements of symbols on the individual reels.

The description of a reel consists of $n$ pairwise distinct integers $a_{1}, a_{2}, \cdots, a_{n}$ ($1 \le a_{i} \le n$), where $a_{i}$ denotes the symbol located at position $i$.

Output

The first and only line of output should contain a single integer equal to the maximum number of rows in which three identical symbols can be found simultaneously.

Examples

Input 1

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

Output 1

3