P14155 [ICPC 2022 Nanjing R] 智巧灵蕈大竞逐

您正作为世界知名游戏《原神》中的旅行者游历提瓦特大陆。在旅经蒙德，璃月和稻妻之后，现在您来到了名为“须弥”的国度。 蕈兽是存在于须弥的一种敌对生物。它们是真菌进化后的生物，具有更强的产生与保护孢子的能力。虽然它们外表十分可爱，但实际上十分危险。蕈兽也是一种三相众物，因此火元素与雷元素将对它们产生相反的影响。受到火元素攻击后，蕈兽将进入枯焦状态，攻击速度减慢，但是会造成更大的伤害。相反地，雷元素的攻击将导致蕈兽进入活化状态，攻击速度会提升。由于不同种类的蕈兽可以抵挡不同元素的不同技能，可以预见，它们将成为旅行者的强力伙伴。您开始考虑如何与蕈兽组成队伍，并让它们听从您的指令。 :::align{center}  ::: 幸运的是，在“智巧灵蕈大竞逐”活动期间，您可以控制蕈兽与对手进行战斗。您被邀请参加“月莲杯”驯兽师大赛，并可以使用名为“意智宝珠”的道具捕获并控制蕈兽，组成自己的蕈兽小队。然而，为了取得大赛的胜利，您还需要通过完成“潜能焕发”挑战来唤醒蕈兽的潜能，解锁它们的特殊技能。 在潜能焕发挑战中，旅行者需要将“花花琼脂”调配成蕈兽喜欢的组合，蕈兽吸收后可唤醒潜能。 :::align{center}  ::: 具体地，挑战开始时，您会得到一个初始的花花琼脂组合，可用一个 $n \times m$ 大小的矩阵来表示。对于所有 $1 \leq i \leq n$ 与 $1 \leq j \leq m$，每个位置 $(i,j)$ 都有一个花花琼脂。矩阵里每个位置的值代表琼脂的种类，如果两个位置的值相同，则两个位置上的琼脂种类也相同。 您可以进行 $3$ 种操作：对调，旋转和预置。 $\textbf{对调}$：对于两个相邻的花花琼脂，您可以使用一次对调操作来交换它们的位置。 具体来说，两个位于 $(x_1,y_1)$ 和 $(x_2,y_2)$ 的花花琼脂被认为是相邻的，当且仅当 $|x_1-x_2|+|y_1-y_2|=1$。交换之后，位于 $(x_1,y_1)$ 和 $(x_2,y_2)$ 的花花琼脂将分别变成之前位于 $(x_2,y_2)$ 和 $(x_1,y_1)$ 的琼脂。 :::align{center}  ::: $\textbf{旋转}$：对于任意四个组成 $2 \times 2$ 大小的子方阵的花花琼脂，您可以通过一次旋转操作来顺时针移动它们的位置。 具体来说，一个 $2 \times 2$ 方阵意味着任意四个位于 $(x,y)$，$(x,y+1)$，$(x+1,y+1)$ 和 $(x+1,y)$ 的花花琼脂（满足 $1 \leq x

每个测试文件仅有一组测试数据。 第一行输入三个整数 $n$, $m$ $k$（$2 \le n, m \le 20$，$1 \le k \le 20$）表示矩阵的大小以及预置配方数量。 对于接下来 $n$ 行，第 $i$ 行输入一个字符串 $s_{i,1}s_{i,2}\cdots s_{i,m}$。其中 $s_{i,j}$ 表示在初始组合中，位于第 $i$ 行第 $j$ 列的琼脂的种类。 接下来是一个空行。 对于接下来 $n$ 行，第 $i$ 行输入一个字符串 $t_{i,1}t_{i,2}\cdots t_{i,m}$。其中 $t_{i,j}$ 表示在目标组合中，位于第 $i$ 行第 $j$ 列的琼脂的种类。 接下来会输入 $k$ 个预置配方。对于第 $p$ 个预置配方： 首先是一个空行。 接下来一行输入两个整数 $n_p$ 和 $m_p$（$1 \le n_p \le n$，$1 \le m_p \le m$）表示预置配方对应的子矩阵大小。 对于接下来 $n_p$ 行，第 $i$ 行输入一个字符串 $f_{i,1}^{(p)}f_{i,2}^{(p)}\cdots f_{i,m_p}^{(p)}$。其中 $f_{i,j}^{(p)}$ 表示在第 $p$ 个配方中，位于第 $i$ 行第 $j$ 列的琼脂的种类。 总共有 $62$ 种不同种类的花花琼脂，用小写字母（`a` 到 `z`），大写字母（`A` 到 `Z`）以及数码（`0` 到 `9`）来表示。两个花花琼脂被认为是种类相同的，当且仅当它们对应的字符相同。所有输入的字符串只会包含这 $62$ 种字符。

如果不存在合法的操作序列，请输出 $-1$（不包含引号）。 否则，在第一行输出一个数字 $r$（$0 \le r \le 4 \times 10^5$）表示所需要的操作步数。 接下来输出 $r$ 行，每行包含三个整数 $op$，$x$ 和 $y$，表示一个作用于当前花花琼脂组合的操作。您需要按执行操作的顺序输出所有操作。可用操作如下： - $-4$ $x$ $y$：交换位于 $(x,y)$ 和 $(x-1,y)$ 的琼脂。要求满足 $1 < x \le n$ 以及 $1 \le y \le m$。 - $-3$ $x$ $y$：交换位于 $(x,y)$ 和 $(x+1,y)$ 的琼脂。要求满足 $1 \le x < n$ 以及 $1 \le y \le m$。 - $-2$ $x$ $y$：交换位于 $(x,y)$ 和 $(x,y-1)$ 的琼脂。要求满足 $1 \le x \le n$ 以及 $1 < y \le m$。 - $-1$ $x$ $y$：交换位于 $(x,y)$ 和 $(x,y+1)$ 的琼脂。要求满足 $1 \le x \le n$ 以及 $1 \le y < m$。 - $0$ $x$ $y$：顺时针旋转位于 $(x,y)$，$(x,y+1)$，$(x+1,y+1)$ 和 $(x+1,y)$ 的琼脂，要求满足 $1 \le x < n$ 以及 $1 \le y < m$。 - $op$ $x$ $y$: 使用一次预置配方 $op$ ，将所有位于 $(i,j)$ 的琼脂（满足 $x \le i \le x + n_{op} - 1$ 以及 $y \le j \le y + m_{op} - 1$）替换成预置配方。要求满足 $1 \le op \le k$, $1 \le x \le n - n_{op} + 1$ 以及 $1 \le y \le m - m_{op} + 1$。 “位于 $(x,y)$ 的琼脂”指的是位于从上到下第 $x$ 行，从左到右第 $y$ 列的琼脂。 除了操作总数不超过 $4 \times 10^5$ 的限制外，我们额外限制预置操作（$1 \le op \le k$）数量不能超过 $400$。可以证明如果存在合法操作序列，则至少存在一个操作序列满足以上条件。 请注意，您并不需要最小化操作数量。若有多种方案，输出任意一种。

对第一组样例数据解释如下。 :::align{center}  :::