#592 Region of Twos

Loading problem...

Preparing the statement, recent submissions, and submit form.

#592 Region of Twos

DOJ/Beginner Contest DOJ/BCD 8

Time limit: 1000 ms
Memory limit: 1024 MB
Checker: TOKEN
Solve threshold: 100

Statement

Statement language

You are given a sequence $A$ of length $N$ and a sequence $B$ of length $M$ . Every element is either $0$ or $1$ .

Define an $N$ by $M$ array $C$ by

C_{i,j}=A_i+B_j.

Consider only cells whose value is $2$ . Two cells are adjacent if they share a side. A connected component is a maximal set of value- $2$ cells in which every pair can be connected using only side-adjacent value- $2$ cells.

Find the largest area of such a connected component. If there is no cell with value $2$ , print $0$ .

Input

The input is given from Standard Input in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

Each case is given in the following format:

$N\ M$ $A_1\ A_2\ \cdots\ A_N$ $B_1\ B_2\ \cdots\ B_M$

Output

For each test case, print the largest area of a connected component described above.

Constraints

$1 \leq T \leq 200\,000$ .
$1 \leq N,M \leq 200\,000$ .
$A_i \in \{0,1\}$ ( $1 \leq i \leq N$ ).
$B_j \in \{0,1\}$ ( $1 \leq j \leq M$ ).
The sum of $N+M$ over all test cases does not exceed $400\,000$ .

Subtasks

#	Score	Constraints
1	7	$N,M \leq 2$ . The sum of $N+M$ over all test cases does not exceed $200$ .
2	21	$A_i=1$ ( $1 \leq i \leq N$ ).
3	29	$N,M \leq 300$ . The sum of $N$ over all test cases does not exceed $300$ . The sum of $M$ over all test cases does not exceed $300$ .
4	43	No additional constraints.

Samples

Input

Output

6
0
12

In the first test case, the six cells at the intersections of rows $1,2$ and columns $2,3,4$ of array $C$ all have value $2$ and form one connected component. No larger connected component exists, so the answer is $6$ .

Editorial

View editorial