As the Traveler, you are exploring the world of Teyvat in the world-famous game Genshin Impact. After visiting Monstadt, Liyue and Inazuma, now you are in the nation of Sumeru.
Fungi are an enemy group found in Sumeru. They are an evolved species of mushrooms with increased abilities to reproduce and protect the flora. Despite their lovely appearance, fungi are actually very dangerous creatures. They are considered Tri-Lakshana Creatures and thus Pyro and Electro will have adverse effects on them. When inflicted with Pyro, they enter a Scorched state, attacking significantly slower but dealing more damage. On the other hand, Electro causes them to enter an Activated state, attacking significantly faster. Since various kinds of fungi are able to discharge different skills of different elements, one can see that they can actually form a very strong team. You start to wonder the possiblity of teaming up with fungi if you can make them listen to your instructions.
Luckily, in the event Fabulous Fungus Frenzy, you are able to control fungi and let them fight enemies! You are invited to compete in the Nilotpala Cup Beast Tamers Tournament. By the gadget called the Wisdom Orb, you can capture and put together your own team of Fungi. However, to win the tournament, you also need to pass the Coruscating Potential challenge to cultivate Fungi and unlock their special skills.
During the Coruscating Potential challenge, you must use Floral Jellies to form blends that your fungi enjoy. Once they have absorbed them, they will awaken their potential.
Specifically, you are given an initial configuration of the Floral Jellies blend, represented by an $$$n \times m$$$ matrix. For all $$$1 \leq i \leq n$$$ and $$$1 \leq j \leq m$$$, each entry $$$(i,j)$$$ lies a Floral Jelly. The value of entries represents the type of Floral Jellies. Equal value of entries indicates that they are the same type of jellies.
You are allowed to perform $$$3$$$ kinds of operations: Switch, Rotate and Preset.
Switch: For any two adjacent Floral Jellies, you can use one Switch operation to exchange the positions of them.
Specifically, two adjacent Floral Jellies located at $$$(x_1,y_1)$$$ and $$$(x_2,y_2)$$$ are considered adjacent if and only if $$$|x_1-x_2|+|y_1-y_2|=1$$$. After the Switch, the Floral Jellies located at $$$(x_1,y_1)$$$ and $$$(x_2,y_2)$$$ will be equal to the previous ones located at $$$(x_2,y_2)$$$ and $$$(x_1,y_1)$$$ respectively.
Rotate: For any four Floral Jellies forming a $$$2 \times 2$$$ block, you can use one Rotate operation to shift the positions of them once in a clockwise direction.
Specifically, a $$$2 \times 2$$$ block means arbitrary four Floral Jellies located at $$$(x,y)$$$, $$$(x,y+1)$$$, $$$(x+1,y+1)$$$ and $$$(x+1,y)$$$ satisfying $$$1 \leq x \lt n$$$ and $$$1 \leq y \lt m$$$. After the Rotate, the Floral Jellies located at $$$(x,y)$$$, $$$(x,y+1)$$$, $$$(x+1,y+1)$$$ and $$$(x+1,y)$$$ will be equal to the previous ones located at $$$(x+1,y)$$$, $$$(x,y)$$$, $$$(x,y+1)$$$ and $$$(x+1,y+1)$$$ respectively.
Preset: For any Floral Jellies forming a $$$n' \times m'$$$ block ($$$1 \le n' \le n$$$, $$$1 \le m' \le m$$$), you can place a pre-existing formula of the same size directly onto the corresponding slot and replace every Floral Jelly with the type on the formula. A preset formula is represented by a $$$n' \times m'$$$ matrix $$$\mathbf{F}$$$.
Specifically, for arbitrary Floral Jellies located at $$$(x+i,y+j)$$$ where $$$1 \leq x \leq n-n'+1$$$, $$$1 \leq y\leq m-m'+1$$$, $$$0 \leq i \lt n'$$$ and $$$0 \leq j \lt m'$$$, after a Preset operation with the preset formula $$$\mathbf{F}$$$, all Floral Jellies located at $$$(x+i,y+j)$$$ will be replaced by a Floral Jelly of the type in $$$(i,j)$$$ of $$$\mathbf{F}$$$.
The challenge requires you to turn the Floral Jellies blends to the target configuration. That is, after processing all operations, each position must be occupied by a Floral Jelly of the required type.
There is only one test case in each test file.
The first line contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$2 \le n, m \le 20$$$, $$$1 \le k \le 20$$$) indicating the size of the initial configuration of the Floral Jellies and the number of preset formulas.
For the following $$$n$$$ lines, the $$$i$$$-th line contains a string $$$s_{i,1}s_{i,2}\cdots s_{i,m}$$$ where $$$s_{i,j}$$$ indicates the type of jelly on the $$$i$$$-th row and the $$$j$$$-th column of the initial configuration.
Then an empty line follows.
For the following $$$n$$$ lines, the $$$i$$$-th line contains a string $$$t_{i,1}t_{i,2}\cdots t_{i,m}$$$ where $$$t_{i,j}$$$ indicates the type of jelly on the $$$i$$$-th row and the $$$j$$$-th column of the target configuration.
Then $$$k$$$ preset formulas follow. For the $$$p$$$-th preset formula:
There will first be an empty line.
The next line contains two integers $$$n_p$$$ and $$$m_p$$$ ($$$1 \le n_p \le n$$$, $$$1 \le m_p \le m$$$) indicating the matrix size of the preset formula.
For the following $$$n_p$$$ lines, the $$$i$$$-th line contains a string $$$f_{i,1}^{(p)}f_{i,2}^{(p)}\cdots f_{i,m_p}^{(p)}$$$ where $$$f_{i,j}^{(p)}$$$ indicates the type of jelly on the $$$i$$$-th row and the $$$j$$$-th column of the $$$p$$$-th preset formula.
There are $$$62$$$ types of Floral Jellies in all, denoted by lowercase letters ('a' to 'z'), uppercase letters ('A' to 'Z') and digits ('0' to '9') respectively. Two Floral Jellies are considered the same if and only if they are of the same character. All given strings will only consist of these $$$62$$$ characters.
If the puzzle is unsolvable, output "$$$-1$$$" (without quotes).
Otherwise, output an integer $$$r$$$ ($$$0 \le r \le 4 \times 10^5$$$) in the first line indicating the number of moves needed to solve the puzzle.
Then output $$$r$$$ lines, each of which contains three integers $$$op$$$, $$$x$$$ and $$$y$$$, indicating an operation on the current Floral Jellies blend. You should output the operations in the order they are carried out. The available operations are listed as follows:
Here a jelly at $$$(x,y)$$$ means it lies in the $$$x$$$-th row from the top to the bottom and the $$$y$$$-th column from the left to the right.
In addition to the limitation of the total number of operations not exceeding $$$4 \times 10^5$$$, we also have a special constraint on the preset operation. The total number of operations with $$$1 \le op \le k$$$ cannot exceed $$$400$$$. It can be proven that if the puzzle is solvable, there always exists a solution satisfying all the constraints.
Note that you don't need to minimize the number of operations. If there are multiple valid solutions, output any.
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
We explain the first sample test case below.
