Jigsaw Puzzle

Problem code: HS08PZL

A jigsaw puzzle is a puzzle that requires arranging a number of differently shaped tiles so that they fit together and form a picture. In this problem we consider rectangular puzzles with almost-square tiles:

The edges between the tiles are symmetrical, and there is a special edge type on the boundary of the puzzle.

Write a program that solves a jigsaw puzzle. It should read the descriptions of puzzle pieces and find an alignment in which all edges fit. There always is a solution, and if a puzzle has multiple solutions you only need to print one of them.

Input

The first line of the input will contain two integers w h: widht and hieght of the puzzle (see notes below on input size), followed by w*h lines containg 4 integers - edge types starting from top and moving clockwise. Edge type 0 means that the tile is on the border of the puzzle.

Output

Output h lines in the following format:
p_1,y a_1,y p_2,y a_2,y ... p_w,y a_w,y
Where p_x,y is the number of puzzle that goes into position (x,y) and a_x,y contains the number of clockwise rotations it needs to fit. The pieces are numbered from 1.

Examples

Example 1

Input:
3 2
0 1 3 0
0 1 5 1
0 0 3 1
3 3 0 0
5 2 0 3
3 0 0 2
Output:
1 0 2 0 3 0
4 0 5 0 6 0

Example 2

Input:
3 2
0 1 3 0
0 1 5 1
3 1 0 0
3 3 0 0
2 0 3 5
0 0 2 3
Output:
1 0 2 0 3 2
4 0 5 1 6 1

Example 3

Input:
3 2
5 2 0 3
0 0 3 1
0 1 3 0
0 1 5 1
3 3 0 0
3 0 0 2
Output:
3 0 4 0 2 0
5 0 1 0 6 0

Example 4

Input:
3 2
5 2 0 3
0 0 3 1
3 0 0 1
0 1 5 1
3 0 0 3
0 0 2 3
Output:
3 2 4 0 2 0
5 1 1 0 6 1

Notes on input size

The score for this problem is proportional to the number of test cases solved. The sizes are as follows:

 W  H  E  TL
 4  3 ~10  1s.
 4  5 ~10  1s.
 7  6 ~15  1s.
 8  8 ~25  1s.
10 10 ~25  1s.
11 11 ~25  1s.
12 12 ~25  1s.
13 12 ~25  1s.
13 13 ~25  1s. 
14 14 ~25  1s.
25 25 ~100 5s.
25 25 ~90  5s.
25 25 ~80  5s.
12 12 ~25  10s.
13 13 ~25  10s.
14 14 ~25  10s.

The last week tests
14 14 ~25  2s.
13 13 ~25  2s.
15 15 ~25  2s.
14 14 ~25  2s.
15 15 ~25  2s.
14 14 ~25  2s.
16 16 ~30  2s.
W - widht of the puzzle
H - height of the puzzle
E - number of different edge types 
TL - time limit

Points

The score awarded to your program is proportional to the number of correctly solved test cases (100 points is equivalent to the situation in which all tests have been solved correctly).

The number of points given in the ranking is scaled so that it is equal to 10 for the registered contestant whose solution has the highest score, and proportionally less for all solutions with lower scores.

Pleas note

For the first five weeks of the series (till Saturday, January 3) all submissions to this problem will be visible to all users and tested on temporary data sets only.

For the last week of the series, submissions will be visible to the submitting contestant, only, and tested on the full set of test cases. (Earlier solutions will be rejudged).

Added by:	Jacek Dąbrowski
Date:	2008-11-29
Time limit:	1s-10s
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

High School Programming League 2008/2009