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:
Every input has a solution that uses all the pipe sections.
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:
id | drawing | ascii | description |
---|---|---|---|
1 | ![]() | --- | horizontal pipe |
2 | ![]() | | | | vertical pipe |
3 | ![]() | __ | | top left corner |
4 | ![]() | __ | | top right corner |
5 | ![]() | __| | bottom right corner |
6 | ![]() | |__ | bottom left corner |
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.)
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
1 0 0 0 1 1 1 3 1