Bajtek来到了赌场，立刻就被一台老虎机吸引了。这台老虎机最重要的部分是三个转轮。每个转轮都分成 $n$ 个相等的部分，上面画着不同的符号。总共有 $n$ 种可能的符号，每种符号在每个转轮上都恰好出现一次。为了简化，我们将符号编号为从 1 到 $n$。下图展示了一个示例老虎机，有三个转轮，每个转轮分成 $n = 5$ 个部分：

拉动拉杆后，每个转轮会循环移动一定的格数。玩家的 winnings 取决于有多少行水平方向上出现三个相同的符号。

Bajtek 知道老虎机可能会把他的钱都吞掉，所以他想先确定他能获得的最大 winnings 是多少。帮助他，确定在最有利的转轮设置下，有多少行能出现三个相同的符号。

Input Format

输入的第一行包含一个整数 $n$ ($1 \le n \le 300\,000$)，表示转轮的大小。接下来的三行描述了每个转轮上的符号排列。

转轮的描述包含 $n$ 个两两不同的整数 $a_{1}, a_{2}, \cdots, a_{n}$ ($1 \le a_{i} \le n$)，其中 $a_{i}$ 表示在位置 $i$ 上的符号。

Output Format

输出的第一行也是唯一一行应该包含一个整数，等于同时出现三个相同符号的最大行数。

Examples

Input

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

Output

3