F. Game
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice and Bob are playing Luzhanqi. Each of them has a permutation of the following $$$24$$$ pieces:

  • one Field Marshal, order 9
  • one General, order 8
  • two Major Generals, order 7
  • two Brigadier Generals, order 6
  • two Colonels, order 5
  • two Majors, order 4
  • three Captains, order 3
  • three Lieutenants, order 2
  • three Engineers, order 1
  • two Bombs
  • three Landmines
To determine the winner, we repeat the following process until someone wins the game or the game ends in a draw:
  • If both permutations are empty, the game ends in a draw.
  • If Alice's permutation is empty, Bob wins the game.
  • If Bob's permutation is empty, Alice wins the game.
  • Let the first piece in Alice's permutation be $$$A$$$ and the first piece in Bob's permutation be $$$B$$$. The following is the outcome of the battle between $$$A$$$ and $$$B$$$:
    1. If $$$A$$$ and $$$B$$$ are the same types of pieces, or if one of $$$A$$$ and $$$B$$$ is Bomb, they are both removed.
    2. Otherwise, if one of $$$A$$$ and $$$B$$$ is Landmine and the other is Engineer, the Landmine is removed and the Engineer stays alive.
    3. Otherwise, if one of $$$A$$$ and $$$B$$$ is Landmine and the other's order is greater than 1, the Landmine stays alive and the other one is removed.
    4. Otherwise, we compare the order of $$$A$$$ and $$$B$$$ and the piece with smaller order is removed.
Bob knows Alice's permutation in advance and can decide his permutation based on that information. After Bob deciding his permutation, Alice can swap two pieces in Bob's permutation. Can Bob construct a permutation that wins against Alice's permutation no matter which pair of pieces she swaps?
Input

The first line contains one integer $$$T$$$ denoting the number of test cases ($$$1\le T\le 100$$$).

Each of the next $$$T$$$ lines contains $$$24$$$ integers denoting Alice's permutation:

  • $$$40$$$ represents Field Marshal
  • $$$39$$$ represents General
  • $$$38$$$ represents Major Generals
  • $$$37$$$ represents Brigadier Generals
  • $$$36$$$ represents Colonels
  • $$$35$$$ represents Majors
  • $$$34$$$ represents Captains
  • $$$33$$$ represents Lieutenants
  • $$$32$$$ represents Engineers
  • $$$31$$$ represents Landmines
  • $$$30$$$ represents Bombs
It is guaranteed that all permutations are chosen uniformly at random and contains exactly the $$$24$$$ pieces described in the statement.
Output

Output one line for each test case.

If Bob cannot construct the required permutation, print $$$-1$$$.

Otherwise, print $$$24$$$ integers representing Bob's permutation in the same format as in the input. If there are multiple solutions, print any. Bob's permutation must contain exactly the $$$24$$$ pieces described in the statement.

Example
Input
4
40 39 38 38 37 37 36 36 35 35 34 34
 34 33 33 33 32 32 32 31 31 31 30 30
34 31 36 33 31 39 37 38 35 32 32 35
 36 31 34 32 38 40 30 33 30 34 33 37
37 30 40 38 36 38 32 34 36 35 37 32
 34 33 31 30 33 31 35 34 33 39 31 32
30 33 32 39 37 38 35 40 34 30 31 37
 31 33 31 33 34 32 36 36 35 34 32 38
Output
34 36 30 39 33 38 37 31 34 30 33 35
 38 31 37 33 40 31 35 32 32 36 32 34 
34 32 32 38 40 33 33 30 31 34 31 35
 37 32 34 36 33 31 38 30 36 37 35 39 
38 33 32 31 36 34 30 34 33 40 32 37
 38 30 37 35 33 35 32 31 34 31 39 36 
37 34 33 36 34 35 31 38 32 38 31 32
 37 30 30 31 33 36 32 33 40 39 34 35
Note

Note that the sample input and sample output contain wrapped lines to fit in the width of page.