Problem Description

Jurica has created a puzzle game, which is a parallelogram consisting of nodes arranged in $N$ rows and $M$ columns.

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 represented by $(x, y)$, where $x$ and $y$ are the row and column numbers, respectively. Each node has a unique integer weight within the range $[1, N \times M]$.

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

For example, when $N=3$ and $M=4$, the puzzle looks like this:

Two types of operations can be performed on the puzzle:

1. Select a diamond-shaped unit consisting of nodes $(x, y)$, $(x+1, y)$, $(x+1, y+1)$, and $(x, y+1)$, and rotate it clockwise.

1. Select an equilateral triangle-shaped unit consisting of nodes $(x, y)$, $(x+1, y)$, and $(x, y+1)$, and rotate it clockwise.

Jurica performed a series of operations, which he called a "big operation," and repeated this big operation several times, eventually solving the puzzle.

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

Input Format

Input consists of three integers: $N$, $M$, and $K$.

Output Format

If there is no valid big operation, output -1.

Otherwise, output any valid big operation. The first line should contain the number of operations $B$ in the big operation, followed by $B$ lines describing the operations in the following format:

• R x y, indicating operation 1;
• T x y, indicating operation 2;

where $x$ and $y$ are the coordinates $(x, y)$ for the selected operation.

The output must satisfy $1 \le B \le 5 \times 10^5$, $1 \le x < N$, and $1 \le y < M$.

Sample Input and Output

Sample Input #1

2 3 2

Sample Output #1

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

Sample Input #2

3 3 12

Sample Output #2

3
R 1 1
T 2 2
T 2 1

Sample Input #3

5 4 116

Sample Output #3

-1

Notes/Hints

Data Size and Constraints

For $40\%$ of the test cases, $N, M \le 3$ and $K \le 20$.

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

Notes

This problem's score is set according to the original COCI contest, with a maximum score of $110$.

The problem is translated from COCI2018-2019 CONTEST #4 T4 Slagalica.

见题面 Input 部分

见题面 Output 部分