Maximum Common Square Submatrix

Blue Mary is exploring new challenges in the Starcraft RPG game by playing campaign maps. Each campaign map is encoded as an n×n matrix where each cell contains a 32-bit signed positive integer. Two maps are considered similar if they share a common square submatrix of the maximum possible size. Formally, the similarity of two maps is defined as the maximum integer \(k\) such that there exist indices \(i,j\) in the first matrix and \(u,v\) in the second matrix for which the corresponding \(k \times k\) submatrices are identical.

Your task is to help Blue Mary determine the similarity of two given maps by computing this maximum common square submatrix side length.

Note: If no common element exists between two maps, the similarity is 0.

inputFormat

The input starts with an integer n denoting the dimensions of the matrices. It is followed by n lines each containing n space-separated integers which represent the first map. Then, n lines follow representing the second map in the same format.

For example:

3
1 2 3
4 5 6
7 8 9
1 2 3
4 5 6
7 8 9

outputFormat

Output a single integer which is the maximum side length of a common square submatrix between the two given matrices. If no such submatrix exists, output 0.

For the sample input above, the output should be:

3

sample

3
1 2 3
4 5 6
7 8 9
1 2 3
4 5 6
7 8 9

3