Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

HS08PZL - Jigsaw Puzzle

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:
p1,y a1,y p2,y a2,y ... pw,y aw,y
Where px,y is the number of puzzle that goes into position (x,y) and ax,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:0.200s-2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST TEXT WHITESPACE

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.