Alphabet Jigsaw Puzzle

The cows are playing an alphabetical jigsaw puzzle. The puzzle consists of R rows and C columns (with 1 \(\le R, C \le 10\)). Each puzzle piece has a unique serial number and 4 edges given in clockwise order as top, right, bottom, left. Each edge is marked with a lowercase letter (a–z) or the digit \(0\) to denote a border.

Pieces can be rotated in steps of 90° clockwise. In the final assembled puzzle, every piece on the border must have the corresponding outer edge equal to \(0\); moreover, if two pieces are adjacent then their common edges must have the same letter. Formally, if a piece placed at grid cell \((r,c)\) has edges \([T,R,B,L]\) (after rotation), then it must satisfy:

• If \(r=0\), then \(T=0\).
• If \(r=R-1\), then \(B=0\).
• If \(c=0\), then \(L=0\).
• If \(c=C-1\), then \(R=0\).
• If \(c>0\), then the left edge \(L\) must equal the right edge of cell \((r,c-1)\).
• If \(r>0\), then the top edge \(T\) must equal the bottom edge of cell \((r-1,c)\).

Your task is to output one valid assembly of the puzzle. For each cell of the puzzle, output the piece's serial number and the number of 90° clockwise rotations applied (which can be 0, 1, 2, or 3). Note that a rotation changes the ordering of the edges as follows:

[ \text{Rotation }0: [T, R, B, L] \quad\rightarrow\quad \text{Rotation }1: [L, T, R, B] \quad\rightarrow\quad \text{Rotation }2: [B, L, T, R] \quad\rightarrow\quad \text{Rotation }3: [R, B, L, T] ]

inputFormat

The input begins with a line containing two integers R and C, denoting the number of rows and columns in the puzzle. This is followed by (R \times C) lines, each describing a puzzle piece. Each piece description consists of a serial number (an integer) and 4 characters separated by spaces representing its top, right, bottom, and left edges (in its original orientation). The character '0' denotes a border.

outputFormat

Output R lines. Each line should contain C pairs. Each pair consists of the piece's serial number and an integer representing the number of 90° clockwise rotations applied to that piece (i.e., 0, 1, 2, or 3). Separate numbers by a single space. For example, a valid output for a 2x3 puzzle might be:

1 0 2 0 3 0 4 0 5 0 6 0

sample

2 2
1 0 a b 0
2 0 0 c a
3 b d 0 0
4 c 0 0 d

1 0 2 0
3 0 4 0