Background

Translated from ROIR 2022 D1T4。

There are two arrays of natural numbers, $A = [a_1, a_2, \dots , a_n]$ and $B = [b_1, b_2, \dots , b_m]$。

For each array, randomly remove a possibly empty prefix and a possibly empty suffix so that the remaining parts have the same length. Denote the resulting arrays by $A'$ and $B'$, and their length is $k$. Then, add the corresponding elements of these two arrays, and denote the resulting array by $C = [c_1, c_2, \dots , c_k]$。

For example, suppose $n = 5,A = [4, 3, 3, 2, 1],m = 6,B = [4, 1, 5, 1, 3, 2]$. Remove the first and the last elements from array $A$, and remove the first three elements from array $B$, obtaining $A' = [3, 3, 2],B' = [1, 3, 2]$. The sum of their corresponding elements is $C = [4, 6, 4]$。
Suppose $n = 7,A = [1,9,1,9,8,1,0],m = 6,B = [1,1,4,5,1,4]$. Remove the first two elements and the last element from array $A$, and remove the first and the last elements from array $B$, obtaining $A' = [1,9,8,1],B' = [1,4,5,1]$. The sum of their corresponding elements is $C = [2,13,13,2]$。

Problem Description

Find the maximum length $k$ such that it is possible to obtain a palindromic array $C$。

Input Format

The first line contains two integers $n$ and $m$, representing the number of elements in the first array and the second array, respectively ($1 \le n, m \le 100 000$)。

The second line contains $n$ integers $a_1,a_2,\dots,a_n$, representing array $A$ ($1 \le a_i \le 100$)。

The third line contains $m$ integers $b_1,b_2,\dots,b_n$, representing array $B$ ($1 \le b_i \le 100$)。

Output Format

Output one integer, the maximum possible length $k$ of a palindromic array that can be obtained。

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

3

Hint

This problem uses bundled testdata。

For all testdata, $1 \le n, m \le 100 000$, $1 \le a_i \le 100$, $1 \le b_i \le 100$。

Translated by ChatGPT 5