S. Loopz

Badarg, the fearless pirate, was attacked by aliens on his way back from the treasure island. He can only escape by assembling his raft, stored in the captain's cabin in a big, gilded box. His raft is made from PVC pipe sections, which can be connected to form a single rectangular waterproof loop.

The raft is made of pipe segments, arrenged in x*y cells. There are 6 different kind of pipe segments (4 corners, a horizontal and a vertical).

A pipe section contains connected pipe segments that form a pipeline that has exactly two endpoints, and those endpoints are not blocked by other segments in the section. Badarg finds a set of such pipe sections in his box. His task is to arrange and place them (by moving and rotating the sections) in a way that:

  1. the final setup is a single loop of pipes.
  2. there must be exactly one pipe segment in each cell.

Every input has a solution that uses all the pipe sections.

Input

The first line contains three integers: x, y, number of pipe sections. Then the pipe section descriptions follows. Each pipe section starts with a width,height line, followed by a 2d matrix of pipe segments.

A pipe segment is identified with an integer, 0 means empty tile, the meanings of the other identifiers can be seen in the table below:

iddrawingasciidescription
1
---
horizontal pipe
2
|
|
vertical pipe
3
 __
|
top left corner
4
__
  |
top right corner
5
__|
bottom right corner
6
|__
bottom left corner

Output

The output should contain a line for each pipe section with three integers describing three operations:

(Badarg wears an eyepatch and cannot think in 3D - flipping the sections doesn't occur to him.)

Example input

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

Example output

1 0 0
0 1 1
1 3 1