PCPC12C - Tetravex

no tags 

TetraVex is an edge-matching puzzle. The player is presented with a grid (by default, 3×3) and nine square tiles, each with four numbers one number on each edge. The objective of the game is to place the tiles in the grid in the proper position as fast as possible without rotating any tile. Two tiles can only be placed next to each other if the numbers on adjacent faces match.

In this problem you should print the final configuration.

Input

Input will start with 0 < t <= 100 (number of test cases).  Each test case describes the initial grid configuration in 9 lines; each line contains 4 integers in this order top, right, bottom, and left. These integers will be in range 0 to 9 inclusive.

Output

You should print one line for each test case containing a permutation of the numbers from 1 to 9 a1a2a3a4…a9 the digit ai should be the tile number in the input that should be put at the cell number i in the output configuration describing the final board configuration row-major order. If there are multiple solutions print the smallest lexicographically. There will always be a solution.

Example

Input:
1
6513
7908
7709
4671
1177
5217
1556
9045
8510

Output:
189547236

hide comments
:D: 2013-02-05 09:12:39

In theory, this one is harder since it requires more output info. But I will belive Tjandra that bruteforce passes. Besides, many retired users would loose an AC if previous was moved.

Francky: 2013-01-17 19:10:55

So, only one of those should stay in classical, imho. Prior to the elder.

J.A.R.V.I.S.: 2013-01-17 18:20:34

Same as TETRAVEX.. except for the input format

BOND: 2013-01-16 14:58:40

mother of brute-force :P

Ehor Nechiporenko: 2013-01-03 09:02:44

Could you please give me some tests, when my application fails. I realy don't understand what's wrong with my solution

Aditya Pande: 2013-01-03 09:02:44

Got AC in 0.00 seconds...
Great

Last edit: 2013-01-01 11:26:00
(Tjandra Satria Gunawan)(曾毅昆): 2013-01-03 09:02:44

Easy problem, my bruteforce program got AC in 0.00s... I think pyramid cluster is better for this problem..


Added by:abdelkarim
Date:2012-12-28
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:The First Palestinian Collegiate Programming Contest