Game of War

Problem code: HS08WAR

War is a very simple card game for two players that is based on pure luck rather than strategy. Both players have a stack of card, and in each round of the game they try to take some of the opponents cards. The player that loses all his cards loses the game.

Each round is played as follows:
1. Both players take a card from the top of their stacks and put it on the table.
2. If the cards on the table differ, then the player with the higher card is the winner (goto 5).
3. There is a tie, and a WAR begins. Both players take a card from the top of their stacks and put it on top of their table stacks. These cards do not fight.
4. goto 1.
5. The player that has won the round collects the card from the table. First he takes a card from the top of his own table stack and puts in on bottom of his stack, then a card from the top of his opponents table stack, then a card from the top of his own table stack, then a card from the top of his opponents table stack, and so on until the table is cleared.

If at any point a player is supposed to play a card but his stack is empty - he loses. If both players don't have a card to play - then it is a draw. If a player has no cards at the end of a round - he loses.

The following picture contains an example of a War game. The values in the boxes show the supposed output of your program after successive rounds.

Write a program that will simulate a war game for a specified number of rounds. Output the stacks of both players if the game has not finished, or two integers depnding on the outcome (see below for a description).

Input

The first line of the input will contain an integer - the number of test cases. Each of the test cases consists of three lines:
R
N₁ C₁ C₁ ... C_N1
N₂ C₁ C₁ ... C_N2
Integer R < 1000000 is the number of rounds the simulation is supposed to run.

The following two lines descibe the stacks for first and second player. The first number is the number of cards (less than 1000), followed by integer-encoded value of cards (Jack is an 11, Queen a 12, King a 13 and an Ace is 14).

Output

For each test case output two lines:

• In case the game is drawn output a zero in each line.
• If the first player has won output the total number of cards in the first line and a zero in the second.
• If the second player has won output a zero in the first line and the total number of cards in the second.
• If both players have cards on their stacks - output them in the same format as in the input (the number of cards, followed by the integer values, starting from the top).

Example 1

Input:
5
1
4 14 6 14 6
4 13 9 14 7
2
4 14 6 14 6
4 13 9 14 7
3
4 14 6 14 6
4 13 9 14 7
4
4 14 6 14 6
4 13 9 14 7
5
4 14 6 14 6
4 13 9 14 7
Output:
5 6 14 6 14 13
3 9 14 7
4 14 6 14 13
4 14 7 9 6
7 13 14 9 6 7 14 14
1 6
8
0
8
0

Example 2

Input:
10
1
3 6 3 6
3 6 4 6
1
10 2 3 4 5 6 7 8 9 10 11
10 11 10 9 8 7 6 5 4 3 2
2
10 2 3 4 5 6 7 8 9 10 11
10 11 10 9 8 7 6 5 4 3 2
3
10 2 3 4 5 6 7 8 9 10 11
10 11 10 9 8 7 6 5 4 3 2
4
10 2 3 4 5 6 7 8 9 10 11
10 11 10 9 8 7 6 5 4 3 2
5
10 2 3 4 5 6 7 8 9 10 11
10 11 10 9 8 7 6 5 4 3 2
6
10 2 3 4 5 6 7 8 9 10 11
10 11 10 9 8 7 6 5 4 3 2
7
10 2 3 4 5 6 7 8 9 10 11
10 11 10 9 8 7 6 5 4 3 2
8
10 2 3 4 5 6 7 8 9 10 11
10 11 10 9 8 7 6 5 4 3 2
100
10 2 3 4 5 6 7 8 9 10 11
10 11 10 9 8 7 6 5 4 3 2
Output:
0
0
9 3 4 5 6 7 8 9 10 11
11 10 9 8 7 6 5 4 3 2 11 2
8 4 5 6 7 8 9 10 11
12 9 8 7 6 5 4 3 2 11 2 10 3
7 5 6 7 8 9 10 11
13 8 7 6 5 4 3 2 11 2 10 3 9 4
6 6 7 8 9 10 11
14 7 6 5 4 3 2 11 2 10 3 9 4 8 5
5 7 8 9 10 11
15 6 5 4 3 2 11 2 10 3 9 4 8 5 7 6
6 8 9 10 11 7 6
14 5 4 3 2 11 2 10 3 9 4 8 5 7 6
7 9 10 11 7 6 8 5
13 4 3 2 11 2 10 3 9 4 8 5 7 6
8 10 11 7 6 8 5 9 4
12 3 2 11 2 10 3 9 4 8 5 7 6
20
0

Scoring

By solving this problem you score 10 points.

---

Added by:	Jacek Dąbrowski
Date:	2008-11-28
Time limit:	1s
Source limit:	50000B
Languages:	SED C99 strict C++ 4.0.0-8 C++ 4.3.2 TCL SCALA NEM PHP SCM guile LISP sbcl LISP clisp ERL TECS TEXT DOC PDF PS PERL 6 JS