Jurica's Puzzle Game Operation

Jurica has created a puzzle game that consists of an $N$-row by $M$-column parallelogram formed by several nodes. Each node is identified by a coordinate $(x,y)$ where $x$ is the row and $y$ is the column. Every node carries a unique integer weight in the range $[1, N\times M]$.

The puzzle is considered solved if, for every row $i$ (with rows numbered from bottom to top), the nodes from left to right have weights $M(i-1)+1$ to $Mi$. For example, when $N=3$ and $M=4$, the solved puzzle has the first row with weights $1$ to $4$, the second row with weights $5$ to $8$, and the third row with weights $9$ to $12$.

There are two types of moves available in the puzzle:

1. Diamond Rotation: Select a unit-size diamond consisting of the nodes $(x,y)$, $(x+1,y)$, $(x+1,y+1)$, and $(x,y+1)$, and rotate them clockwise. (See illustration.)
2. Triangle Rotation: Select a unit-size equilateral triangle consisting of the nodes $(x,y)$, $(x+1,y)$, and $(x,y+1)$, and rotate them clockwise. (See illustration.)

Jurica performs a sequence of these moves, calling the whole series one big operation. He then repeats the same big operation several times, and remarkably, the puzzle returns to the solved state exactly after $K$ repetitions, with no earlier repetition yielding the solved configuration.

Given the dimensions of the puzzle and the number of repetitions $K$, your task is to determine if there exists a big operation (i.e. a sequence of basic moves) such that starting from the solved state, the state will become solved for the first time after exactly $K$ repetitions. If such a big operation exists, output the sequence of moves that compose the big operation.

Notes on Moves:

• A diamond rotation rotates 4 nodes and has an order of 4: applying it 4 times returns the nodes to their original positions.
• A triangle rotation rotates 3 nodes and has an order of 3: applying it 3 times returns the nodes to their original positions.

You may output any valid sequence that satisfies the conditions. If no such sequence exists, output -1.

inputFormat

The input consists of a single line containing three integers: N, M, and K. It is guaranteed that N ≥ 2 and M ≥ 2. The puzzle is in the solved state if, for each row i (numbered from 1 at the bottom to N at the top), the nodes from left to right have the weights $M(i-1)+1$ to $Mi$. The allowed operations are as described in the problem statement.

outputFormat

If there exists a valid big operation, first output an integer L representing the number of moves in the big operation. Then output L lines, each describing a move in one of the following formats:

• "diamond x y" – indicating a diamond rotation on the unit diamond with top-left node at (x, y). • "triangle x y" – indicating a triangle rotation on the unit triangle with top-left node at (x, y).

If no such operation exists, output -1.

sample

3 4 3

1
triangle 1 1

</p>