Bajtek przyszedł do kasyna, gdzie od razu zainteresował go automat do gry w jednorękiego bandytę. Najważniejszą częścią automatu są trzy bębny. Każdy z nich podzielony jest na $n$ równych pól, na których namalowane są różne symbole. Jest $n$ możliwych symboli i każdy z nich występuje na każdym bębnie dokładnie raz. Dla uproszczenia ponumerujmy symbole liczbami od 1 do $n$. Poniższy rysunek przedstawia przykładowy automat z trzema bębnami podzielonymi na $n = 5$ pól:

Po pociągnięciu wajchy, każdy z bębnów przesuwa się cyklicznie o pewną liczbę pozycji. Wygrana gracza zależy od liczby poziomych rzędów, w których znajdą się trzy takie same symbole.

Bajtek wie, że jednoręki bandyta może zabrać wszystkie jego pieniądze, więc wolałby najpierw stwierdzić, jaka może być jego maksymalna wygrana. Pomóż mu i wyznacz liczbę rzędów, w których mogą znaleźć się trzy takie same symbole przy najkorzystniejszym ustawieniu bębnów.

Input Format

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą $n$ ($1 \le n \le 300\,000$), oznaczającą wielkość bębnów. Trzy następne wiersze opisują układy symboli na poszczególnych bębnach.

Opis bębna składa się z $n$ parami różnych liczb całkowitych $a_{1}, a_{2}, \cdots, a_{n}$ ($1 \le a_{i} \le n$), gdzie $a_{i}$ oznacza symbol znajdujący się na pozycji $i$.

Output Format

Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę całkowitą, równą maksymalnej liczbie rzędów, w których mogą się jednocześnie znaleźć po trzy takie same symbole.

Examples

Input

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

Output

3