Sutag-Craft

문제 정보

문제

Sutag-Craft is the world's most famous real-time strategy game.
To be the most famous Sutag-Craft pro-gamer, she should play hundreds, thousands, hundreds of millions of game.

In this game, each players control his/her roosters to crow (that's why the name of the game is 수탉-craft).
The roosters live in a world which consists of N x M tiles.
Each tile contains a different number of worms -- the number of worms decide how many roosters can live in each tile.

Players also try to block other players' roosters from crowing by installing various items in the map.
A popular item is a truck used in a fried chicken store: roosters nearby the truck gets horrified so much that they won't crow anymore.
A truck comes in two sizes, each occupying 1 x 2 and 1 x 3 tiles.

Another popular item is chicken trap. A chicken trap is a transparent box with a big worm doll in the middle.
Nearby roosters are lured to the worm and rushes to the trap, but when they touch the surface of the trap they are temporarily paralyzed.
You can install traps of any size, as long as its borders are aligned with the X and Y axis.

After playing Sutag-Craft hundreds, thousands, hundreds of millions games, you realized two important things.

  • There is a bug in Sutag-Craft: if you install a trap so that the left-upper corner tile and right-lower corner tile of the trap contain the same number of worms, the trap will kill the roosters instead of paralyzing them.
  • All the maps in Sutag-Craft are generated by a fixed rule: the number of worms in tile (i, j) will equal to Row_i xor Col_i, where Row_1, Row_2, ... Row_N and Col_1, Col_2, ... Col_M are predetermined for each type of maps. xor denotes eXclusive OR operator)

You want to exploit this by finding the largest trap which activates the bug. As the number of roosters you can paralyze depends on the total perimeter of the trap, you want to find the trap with the maximum perimeter.

Write a program to calculate the maximum perimeter length of a trap which activates the bug given the map's parameters.

입력

The first line of the input contains the number of test cases T.

Each test case describes a game map and contains 3 lines.
The first line will contain two integers, N and M (1 <= n, m <= 1000).
N integers Row_1, Row_2, ... Row_N will be given in the next line, followed by a line with M integers Col_1, Col_2, ... Col_M. (0 <= Row_i, Col_j <= 1023)

출력

For each test case, print a line with the maximum perimeter length of a trap.

예제 입력

3
2 2
1 2
3 4
3 3
1 1 1
1 1 1
15 15
61 105 85 81 94 17 87 10 5 2 41 49 51 1 13 
32 2 79 62 121 48 86 0 66 18 55 128 63 16 63

예제 출력

4
12
58

노트

Note

3개의 댓글이 있습니다.