题目描述

您正作为世界知名游戏《原神》中的旅行者游历提瓦特大陆。在旅经蒙德，璃月和稻妻之后，现在您来到了名为“须弥”的国度。

蕈兽是存在于须弥的一种敌对生物。它们是真菌进化后的生物，具有更强的产生与保护孢子的能力。虽然它们外表十分可爱，但实际上十分危险。蕈兽也是一种三相众物，因此火元素与雷元素将对它们产生相反的影响。受到火元素攻击后，蕈兽将进入枯焦状态，攻击速度减慢，但是会造成更大的伤害。相反地，雷元素的攻击将导致蕈兽进入活化状态，攻击速度会提升。由于不同种类的蕈兽可以抵挡不同元素的不同技能，可以预见，它们将成为旅行者的强力伙伴。您开始考虑如何与蕈兽组成队伍，并让它们听从您的指令。

:::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$ 和 $1 \leq y<m$）。在旋转操作后，位于 $(x,y)$，$(x,y+1)$，$(x+1,y+1)$ 和 $(x+1,y)$ 的花花琼脂会分别变成之前位于 $(x+1,y)$，$(x,y)$，$(x,y+1)$ 和 $(x+1,y+1)$ 的琼脂。

:::align{center} :::

$\textbf{预置}$：对于任意形成 $n' \times m'$ 大小的子矩阵（$1 \le n' \le n$，$1 \le m' \le m$）的花花琼脂，您可以通过一次预置操作将它们一次性覆盖成一个预先给出的且大小相同的配方。用一个大小为 $n' \times m'$ 的矩阵 $\mathbf{F}$ 来表示一个配方。

具体来说，对于每一个位于 $(x+i,y+j)$ 的花花琼脂（满足 $1 \leq x \leq n-n'+1$，$1 \leq y\leq m-m'+1$，$0 \leq i<n'$ 和 $0 \leq j <m'$)，在使用配方 $\mathbf{F}$ 的预置操作后，位于 $(x+i,y+j)$ 的花花琼脂将变成 $\mathbf{F}$ 中位于 $(i,j)$ 的琼脂。

:::align{center} :::

挑战指定了最终需要形成的花花琼脂目标组合。也就是说，在完成所有操作之后，矩阵里每个位置的花花琼脂的类型都必须和目标组合的相应位置一致。

输入格式

每个测试文件仅有一组测试数据。

第一行输入三个整数 $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$。可以证明如果存在合法操作序列，则至少存在一个操作序列满足以上条件。

请注意，您并不需要最小化操作数量。若有多种方案，输出任意一种。

3 3 1
OOO
GOG
BGB

OOO
GGG
BBB

3 1
B
G
B

4
1 1 3
0 1 2
-1 3 2
-4 3 3

2 2 1
OO
OO

PP
PP

1 2
OP

-1

4 8 4
11122222
33344444
55556666
77777777

NIxSHUOx
DExDUIxx
DANxSHIx
YUANSHEN

2 3
NIy
DEx

3 8
zzzzzzzz
DANNSH9I
YUA9SHEN

1 1
x

2 5
SHO8y
DUUI8

13
2 2 1
-3 3 4
-2 3 8
1 1 1
4 1 4
0 1 6
3 1 3
3 1 8
3 2 3
3 2 7
3 2 8
3 3 4
3 3 8

提示

对第一组样例数据解释如下。

:::align{center} :::