Background

"Named after the wind, the isles sing together." — Wind Isle.

Problem Description

Wind Isle is an archipelago with $n$ rows and $m$ columns. The cell in row $i$ and column $j$ is denoted as $(i,j)$.

The gravity system of Wind Isle is very strange. The gravity coefficient of $(i,j)$ is $g_{i,j}=a_i+b_j$. Here, $a$ and $b$ are two known arrays of lengths $n$ and $m$.

We say islands $(x,y)$ and $(z,w)$ are adjacent if and only if $|x-z|+|y-w|=1$. We say $(x,y)$ and $(z,w)$ are connected if and only if at least one of the following holds:

• $(x,y)$ and $(z,w)$ are adjacent, and $g_{x,y}=g_{z,w}$.

• There exists another island $(u,v)$ such that $(x,y)$ is connected to $(u,v)$ and $(u,v)$ is connected to $(z,w)$. That is, the connected relation is transitive.

We define an unordered set of distinct islands $\{(x_i,y_i)\}$ to be a same-color connected component if and only if every pair of islands in the set is connected.

Find the largest same-color connected component, and output its size and the number of such components.

Input Format

This problem has multiple test cases. The first line contains a positive integer $T$, representing the number of testdata groups in this test.

For each test case:

The first line contains $n$ and $m$, representing the number of rows and columns of Wind Isle.

The next line contains $n$ integers, representing array $a$.

The next line contains $m$ integers, representing array $b$.

Output Format

Output $T$ lines. Each line contains the answer for that test case (the maximum component size and the count).

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

2 4
6 1
6 4

Hint

Sample Explanation

For sample $1$:

For the first test case, the gravity coefficients are as follows:

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

2 3 4 5
* # ? .
* # ? .

The cells marked by symbols form the largest same-color connected components. The size is $2$, and there are $4$ such components.

Constraints

For $20\%$ of the data, $n,m \le 10^3$.

For another $20\%$ of the data, all $b_i$ are equal.

For another $20\%$ of the data, the answer to the second question is guaranteed to be $1$.

For another $20\%$ of the data, $T=1$. The test points represented by these four subtasks do not include each other.

For $100\%$ of the data, $1 \le T \le 5$, $1 \le n,m \le 10^5$, $1 \le a_i,b_i \le 10^9$.

Source

Translated by ChatGPT 5