問題文

長さ $N$ の整数列 $A=(A_1,A_2,\cdots,A_N)$ と 長さ $M$ の整数列 $B=(B_1,B_2,\cdots,B_M)$ があります。 $A$ と $B$ の各要素には $1$ 以上 $N+M$ 以下の整数で番号づけられた色が塗られており、 $A$ の $i$ 番目の要素は色 $C_i$ で、 $B$ の $i$ 番目の要素は色 $D_i$ で塗られています。

$A$ の非空な連続部分列 $X=(X_1,X_2,\cdots,X_{|X|})$ と $B$ の非空な連続部分列 $Y=(Y_1,Y_2,\cdots,Y_{|Y|})$ の組 $(X,Y)$ であって、 以下の条件を満たすものをクロスと呼びます。

• $|X|=|Y|$ かつ $|X|$ は奇数であって、 $X$ の $\frac{|X|+1}{2}$ 番目の要素と $Y$ の $\frac{|Y|+1}{2}$ 番目の要素は同じ色で塗られている。

クロス $(X,Y)$ のスコアを $\sum\limits_{i=1}^{|X|} (X_i+Y_i)$ と定めます。 クロスのスコアが取りうる最大値を求めてください。ただし、クロスが $1$ つも存在しない場合はその旨を報告してください。

$T$ 個のテストケースについて答えてください。

制約

• $1\le T\le 2\times 10^5$
• $1\le N,M\le 2\times 10^5$
• $1\le A_i,B_j\le 10^9(1\le i\le N,1\le j\le M)$
• $1\le C_i,D_j\le N+M(1\le i\le N,1\le j\le M)$
• $T$ 個のテストケースにわたる $N$ の総和および $M$ の総和はそれぞれ $2\times 10^5$ を超えない
• 入力は全て整数

入力

入力は以下の形式で与えられます。ここで、$case_i$ は $i$ 番目のテストケースを表します。

$T$
$case_1$
$case_2$
$\vdots$
$case_T$

各テストケースは次の形式で与えられます。

$N\ M$
$A_1\ A_2\ \cdots\ A_N$
$B_1\ B_2\ \cdots\ B_M$
$C_1\ C_2\ \cdots\ C_N$
$D_1\ D_2\ \cdots\ D_M$

出力

$T$ 行出力してください。 $i$ 行目には $i$ 番目のテストケースについて、 クロスが存在する場合はそのスコアが取りうる最大値を、存在しない場合は -1 を出力してください。

サンプル

3
8 5
4 3 1 1 5 6 1 4
5 1 5 2 3
8 8 4 7 1 5 1 2
1 1 6 6 2
3 2
3 4 5
4 3
1 1 1
2 2
15 20
7 9 8 4 10 7 2 5 3 11 3 1 9 1 2
11 11 7 4 3 7 2 2 6 8 5 1 7 1 9 9 3 1 3 2
12 6 7 12 6 10 14 6 17 4 17 16 4 3 8
14 11 3 14 18 11 17 19 2 7 17 13 2 12 6 17 3 12 17 6

23
-1
140