# 2022 年上海市大学生程序设计竞赛 - 十月赛

D. Permutation

Given three permutations of length $n$:

• $A = {a_1, a_2, \cdots, a_n}$;
• $B = {b_1, b_2, \cdots, b_n}$;
• $C = {c_1, c_2, \cdots, c_n}$.

Find three subsequences:

• $A’ = {a_{i_1}, a_{i_2}, \cdots, a_{i_m}}$;
• $B’ = {b_{j_1}, b_{j_2}, \cdots, b_{j_m}}$;
• $C’ = {c_{k_1}, c_{k_2}, \cdots, c_{k_m}}$.

The following conditions are satisfied:

• Three subsequences with equal length;
• $i_1 < i_2 < \cdots < i_m$，$j_1 < j_2 < \cdots < j_m$，$k_1 < k_2 < \cdots < k_m$;
• For any $t \in [1, m]$ that satisfies $a_{i_t} = b_{j_t} \times c_{k_t}$ holds or $b_{j_t} = a_{i_t} \times c_{k_t}$ holds or $c_{k_t} = a_{i_t} \times b_{j_t}$.

Find the length of the longest subsequence that can be selected to satisfy the condition.

### 输入格式

The first line of an integer $n$ represents the length of the arrangement.

The next three rows of $n$ integers each represent the permutations $A, B$ and $C$ respectively.

### 输出格式

One integer in a row represents the length of the longest subsequence.

### 样例

Input
6
1 2 3 4 5 6
3 4 2 1 6 5
2 4 3 5 6 1

Output
3


### 提示

$1 \le n \le 20000$, $1 \le a_i, b_i, c_i \le n$.

Note that for any $1\le i,j\le n,i\ne j$, $\ a_i\ne a_j, b_i\ne b_j , c_i\ne c_j$ holds.

Sample explanation:

A legal subsequence is taken as

1 2 5
4 6 5
4 3 1


NaN