stones in the selected mug, one stone is
added to each of the following
mugs/bowls in a counter-clockwise direction.
Stones in the bowls count as scored points and cannot be removed in any further
turn.
As a touring merchant, I come to countries faraway. My wife allows me to travel
around only if I return home with a nice, foreign gift in my hands. The
game, which was my most recent present to her, was a really fascinating
one.
The basic rules of the game are fairly simple: The game is played by exactly
two players. In front of each player there is a fixed number of mugs and a bowl
on the right side of the mugs. The mugs and bowls are arranged in a circle.
A number of stones is placed in each mug. The numbers of stones in the bowls
are the scores of the corresponding players. The players alternate in making
turns. In each turn, the current player selects one of his non-empty mugs. The
stones are removed from the selected mug and are spread over the neighbouring mugs and
bowls as follows: If there are
stones in the selected mug, one stone is
added to each of the following
mugs/bowls in a counter-clockwise direction.
Stones in the bowls count as scored points and cannot be removed in any further
turn.
The following figure shows a turn in the mid of a game:
If the last stone of a selected mug is added to the own bowl, the player
gets an extra move. This extra move may result in additional extra moves (there
is no limit for the number of extra moves).
If, on the other hand, the last stone is added to a mug of the opponent, the
player has the option (not the obligation) to swap the opponent's mug with his
corresponding mug (mugs 
and 
, mugs 
and 
, ...). Swapping is
only allowed if the own mug is not empty. If
he chooses to swap, then both mugs must not be swapped for the following four
turns. (Note that this may be different from four moves: Consider the
move sequence
where 
is a move by the
player and 
is a move by his opponent, who gets extra moves 
and
. If the player swaps mugs in move 
, these two mugs may not be swapped
again in moves 
to 
, but again in 
and later moves.) Each player may choose
the option to swap mugs up to three times within a game.
If the last stone is added to a mug of the current player, and if that mug was empty
before distribution, and if the opposite mug of the opponent is not empty
afterwards, the stones from both mugs are captured and put into the current
player's bowl. This rule does not result in an extra move. Note that in general
the opposite mug is different from the corresponding mug:
Mugs
and 
, mugs
and
, and mugs 
and
are considered as
opposite mugs in the above example.
The game ends as soon as every mug is empty and all stones are in the two
bowls. If a player cannot move because all of his mugs are empty, but the
opponent can move, it is the opponent's turn again. (With respect to the swapping rule
above, the inactivity of the player who cannot move does count as a turn, too.)
Otherwise, if a player can move, he has to choose one of the allowed moves.
Can you help me with the following question: What is the best difference between my final score and my opponent's final score that I can achieve from a given situation? In addition to me, my opponent also plays optimally.
Input
The first line gives the number of test cases 
(
). Each test
case is given in two lines. The first
line of a test case holds the number of mugs 
for each player
(
). The second lines consists of
numbers, describing the
current board after your previous turn.
The first
numbers describe the number of stones in my mugs in
counter-clockwise order. The next number is my score (the stones in my bowl).
Then follows the same for my opponent. You may assume that in total there are not more
than 
stones on the whole board.
Output
For each test case, print one line that gives the best difference between my score and the
opponent's score at the end of the game.
At first, it is the opponent's turn.
Sample Input
Sample Output
