Description

Jurica created a jigsaw puzzle game. It is a parallelogram with $N$ rows and $M$ columns, made up of multiple nodes.

In the puzzle, rows are numbered from $1$ to $N$ from bottom to top, and columns are numbered from $1$ to $M$ from left to right. Each node is denoted by $(x,y)$, where $x$ and $y$ are the row and column, respectively. Each node has a unique integer weight in $[1, N \times M]$.

The puzzle is considered solved when, for the $i$-th row, the weights of the nodes from left to right are $M(i-1)+1 \sim Mi$.

When $N=3, M=4$, the puzzle looks like the figure below:

There are two types of operations that can be performed on the puzzle:

1. Select a unit rhombus that contains nodes $(x,y),(x+1,y),(x+1,y+1),(x,y+1)$, and rotate it clockwise.

2. Select a unit equilateral triangle that contains nodes $(x,y),(x+1,y),(x,y+1)$, and rotate it clockwise.

Jurica performed several operations and called them one big operation. Then he repeated this big operation several times and surprisingly solved the puzzle.

Given the puzzle size and the number of repetitions $K$ of the big operation, determine whether there exists a big operation such that, starting from the solved puzzle, after repeating this big operation $K$ times, it returns to the solved state for the first time. If it is possible, output the operations that make up the big operation.

Input Format

Input integers $N, M, K$.

Output Format

If there is no big operation that satisfies the requirement, output -1.

Otherwise, output any valid big operation. This problem uses Special Judge (see the attachment).

If a valid big operation exists, output the number of operations $B$ in the big operation in the first line, and then output the following format in the next $B$ lines:

• $\texttt{R x y}$, meaning to apply operation 1;
• $\texttt{T x y}$, meaning to apply operation 2;

The output $x,y$ are the chosen coordinates $(x,y)$ for the corresponding operation.

The output must satisfy $1 \le B \le 5 \times 10^5$, $1 \le X \lt N$, $1 \le y \lt M$.

2 3 2

5
R 1 1
R 1 1
T 1 1
T 1 1
T 1 1

3 3 12

3
R 1 1
T 2 2
T 2 1

5 4 116

-1

Hint

Constraints

For $40\%$ of the testdata, $N, M \le 3$, $K \le 20$.

For $100\%$ of the testdata, $2 \le N, M \le 100$, $2 \le K \le 10^{12}$.

Notes

The scoring of this problem follows the original COCI problem, with a full score of $110$.

Translated from COCI2018-2019 CONTEST #4 T4 Slagalica.

Translated by ChatGPT 5