시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 (추가 시간 없음) 256 MB111100.000%

문제

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? 

입력

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 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.

예제 입력 1

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

예제 출력 1

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