题意概述

有一个 $N$ 行 $M$ 列节点的平行四边形网格，每个节点有初始编号（按行列顺序）。
可以执行两种操作：

1. R x y：对以 $(x,y), (x+1,y), (x+1,y+1), (x,y+1)$ 为顶点的菱形顺时针旋转四个节点。
2. T x y：对以 $(x,y), (x+1,y), (x,y+1)$ 为顶点的三角形顺时针旋转三个节点。

定义一个大操作为一个操作序列（若干 R/T 操作）。
给定 $N,M,K$，要求构造一个大操作，使得：

• 执行一次大操作得到状态 $S_1$
• 再执行 $K-1$ 次大操作后回到初始状态
• 操作序列长度 $B \le 5\times 10^5$
• 如果不存在输出 $-1$

---

关键思路

1. 问题转化

设初始状态为恒等置换 $I$，大操作对应一个置换 $f$。
要求 $f^K = I$，且 $K$ 是最小的正整数使得 $f^K = I$（即 $f$ 的阶为 $K$）。
由于题目只要求“恰好 $K$ 次后回到最初状态”，并不要求 $K$ 是阶，但根据通常理解，“恰好 $K$ 次”意味着 $K$ 是周期。

2. 可构造性分析

每个操作（R/T）都是一个小置换，大操作是它们的复合。
我们需要 $f^K = I$。
由于 $K$ 可达 $10^{12}$，直接构造很困难，需要考虑置换的阶的性质。

重要观察：

• 所有 R 和 T 操作都是偶置换（旋转3个元素是偶置换吗？3-cycle 是偶置换吗？）
  • 实际上，3-cycle (1 2 3) = (1 2)(1 3)，是两个对换的复合，所以是偶置换。
  • 4-cycle (1 2 3 4) = (1 2)(1 3)(1 4)，是三个对换，所以是奇置换吗？不对，要检查：
    (1 2 3 4) 可以分解为 (1 4)(1 3)(1 2)，三个对换，奇数个，所以是奇置换。
  • 因此 R 是奇置换，T 是偶置换。

如果一个大操作包含奇数个 R 操作（奇置换个数为奇数），则整个大操作是奇置换；否则是偶置换。
偶置换的阶没有限制，但奇置换的阶？实际上奇置换的阶也可以任意大。

但我们更关心：是否存在一个置换 $f$ 使得 $f^K=I$ 且 $f$ 可由 R/T 操作复合得到？

3. 构造策略

我们可以尝试构造一个简单的 $f$，使其阶恰好为 $K$（或 $K$ 的因数，然后通过重复达到 $K$）。

想法1：找一个阶为 $d$ 的置换 $f$，然后重复 $K/d$ 次这个大操作，使得整体周期为 $K$。
但题目要求一个大操作重复 $K$ 次回到初始，而不是重复 $K/d$ 次。

更准确：我们需要 $f$ 的阶为 $K$。

想法2：利用循环群结构。
如果我们能构造一个单独的循环（一个大轮换），其长度 $L$ 满足 $K \mid L$，那么 $f^{K}$ 可能不是恒等（除非 $L=K$）。
实际上，一个 $L$-cycle 的 $K$ 次幂是恒等当且仅当 $K$ 是 $L$ 的倍数。

所以我们需要 $f$ 是若干不相交循环的乘积，每个循环长度 $L_i$ 满足 $K \mid L_i$。
这样 $f^K$ 才是恒等。

4. 构造具体操作

考虑一个最简单的情形：$N=M=2$。
只有可能的操作：

• R 1 1：影响节点 (1,1),(2,1),(2,2),(1,2)，是一个4-cycle。
• T 1 1：影响 (1,1),(2,1),(1,2)，是一个3-cycle。

我们可以让大操作 = 一个 R 操作。
R 的阶是 4（4-cycle 的阶是 4）。
那么 $f^K=I$ 当且仅当 $4 \mid K$。
所以对于 $K$ 是 4 的倍数时，直接输出 "R 1 1" 即可。

但题目要求 $K$ 可能不是 4 的倍数，比如 $K=2$ 时，样例1给出了5个操作的序列。

---

样例分析

样例1：$N=2, M=3, K=2$
输出：

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

这等价于 $f = (R)^2 \circ (T)^3$。
需要计算这个复合置换的阶是否为 2。

样例2：$N=3, M=3, K=12$
输出：

3
R 1 1
T 2 2
T 2 1

看起来是一个精心构造的置换，阶为 12。

---

一般构造方法

已知 $K \le 10^{12}$，$N,M \le 100$，节点数最多 $10^4$。
我们需要构造一个置换 $f$，使得：

1. $f$ 可由若干 R/T 操作复合得到。
2. $f$ 的阶为 $K$（或 $K$ 的约数，但需要恰好 $K$ 次回到初始，所以必须是 $K$）。

关键定理：在对称群 $S_n$ 中，可以构造任意阶的置换（阶不超过 $n$ 的某些约束）。
但是阶 $K$ 可能大于 $n$（$n=N\times M$），比如 $K$ 可达 $10^{12}$，而 $n \le 10^4$，所以 $K$ 可能远大于 $n$。
置换的阶是它的所有循环长度的最小公倍数（LCM）。
因此，要构造阶为 $K$ 的置换，我们需要循环长度的 LCM 等于 $K$。

由于 $n \le 10^4$，循环长度总和 $\le n$，所以 LCM 不可能超过 $n$ 的某些上界。
实际上，最大可能的 LCM 大约是 $n$ 以内数的最大 LCM，对于 $n=10^4$，最大 LCM 约 $10^{10}$ 级别（可能更大，但 $10^{12}$ 可能达不到）。
所以当 $K$ 很大时（比如大于 $10^4$ 的质因数），可能无法构造。

这就是为什么有些情况输出 -1。

---

算法步骤

1. 计算 $n = N \times M$。
2. 如果 $K$ 大于 $n$ 且 $K$ 是质数（或含大质因数 $p > n$），则输出 -1（因为无法构造长度 $p$ 的循环）。
3. 否则，尝试将 $K$ 分解为一些不超过 $n$ 的数的 LCM。
   即找一组正整数 $l_1,\dots,l_t$，$l_i \le n$，且 $\mathrm{lcm}(l_1,\dots,l_t) = K$。
4. 如果能找到这样的分解，则构造一个置换，由长度分别为 $l_1,\dots,l_t$ 的不相交循环组成。
5. 将这个置换表示为 R/T 操作的序列。
   如何表示一个给定的置换为 R/T 操作序列？
   我们可以使用“冒泡排序”思想：任意置换可以分解为对换，而对换可以由 R/T 操作实现。
   但是需要保证操作坐标在范围内，且步数不超过 $5\times 10^5$。
6. 验证阶为 $K$ 后输出。

---

构造置换为 R/T 操作

难点：如何用 R/T 操作生成任意置换？
实际上，R 和 T 操作可以生成整个偶置换群（当 $N,M$ 足够大时），因为：

• T 操作是偶置换
• R 操作是奇置换
• 它们的组合可以生成所有偶置换（如果节点数≥3）

对于奇置换，可能需要奇数个 R 操作。

因此，我们可以在偶置换群中构造需要的循环分解，如果置换是奇的，则额外加一个 R 操作调整奇偶性。

---

结论

本题是构造题，核心是：

1. 判断 $K$ 是否可表示为不超过 $n = N\times M$ 的若干数的 LCM。
2. 若是，构造对应循环分解的置换。
3. 将置换分解为 R/T 操作序列。
4. 验证阶为 $K$。

由于 $K$ 可达 $10^{12}$，$n \le 10^4$，很多 $K$ 无法表示为不超过 $n$ 的数的 LCM，因此输出 -1 的情况很多。