题目背景

本题是 P5372 [SNOI2019] 积木 的加强版本。

题目描述

艾莉芬在玩积木。她有一块 $n$ 行 $m$ 列的网格板。网格上平铺着一些 $1 \times 2$ 的积木，积木总是对齐占据两个相邻的单元格。积木可以旋转，不能重叠。

你可以做两种操作：

1. 将一块与空白格相邻的积木旋转 $90 \degree$ 到空白格中；
2. 将一块短边与空白格相邻的积木沿长边方向平移至空白格中。

换句话说，你每次只能移动一块积木并且积木移动的目标位置和初始位置必须有一格是重叠的。

如图所示（被移动的积木颜色较浅）：

:::align{center}

:::

请你用以上两种操作将给定的网格板变换为指定的状态。保证初始状态和目标状态的网格尺寸和积木个数相同。并且，空白格子不会非常多。

输入格式

注：由于洛谷的评测限制，在洛谷上提交本题请使用标准输入输出，不要使用文件输入输出。

第一行两个正整数 $n, m$，分别表示网格的行数和列数。

接下来 $n$ 行，每行 $m$ 个字符，描述网格板的初始状态：

• $\tt <$ 表示这个格子是一块积木的左半部分
• $\tt >$ 表示这个格子是一块积木的右半部分
• $\tt n$ 表示这个格子是一块积木的上半部分
• $\tt u$ 表示这个格子是一块积木的下半部分
• $\tt o$ 表示这个格子是空的

接下来另外 $n$ 行，每行 $m$ 个字符，描述你需要将网格板变成的目标状态，格式同上。

输出格式

第一行输出一个正整数 $k$ 表示你的操作次数。

接下来 $k$ 行，按顺序表示你的操作。每行需要输出一个数，这个数 $\mod (n \times m + 1)$ 的值表示你这次移动后占据的空白格编号（第 $i$ 行第 $j$ 列对应 $(i - 1) \times m + j$），这个数除以 $(n \times m + 1)$ 向下取整表示你这次移动的积木。

• $0$ 表示你移动了该空白格左侧的积木；
• $1$ 表示你移动了该空白格右侧的积木；
• $2$ 表示你移动了该空白格上方的积木；
• $3$ 表示你移动了该空白格下方的积木。

3 3
nnn
uuu
o<>
<>n
<>u
<>o

4
27
11
5
17

5 5
n<><>
un<>n
nuonu
u<>un
<><>u
<><>o
<><>n
<><>u
<><>n
<><>u

7
39
19
17
37
7
27
29

4 4
<>oo
<>oo
oonn
oouu
onoo
ou<>
<>no
oouo

5
59
24
44
26
40

提示

【样例解释 2】

初始状态和目标状态分别是题图中的网格 $A, B$。

【测试点约束】

你输出的操作序列长度 $k$ 不能超过 $4 \times 10^6$。

对于所有数据，$1 \leq n, m \leq 1000$，保证空白格子数量 $\geq 1$ 且 $\leq 500$。

对于 $10\%$ 的数据，$n, m \leq 4$

对于另外 $15\%$ 的数据，$m \leq 4$

对于另外 $10\%$ 的数据，$n, m \leq 40$

对于另外 $15\%$ 的数据，$n, m \leq 120$

对于另外 $25\%$ 的数据，$n, m$ 是奇数并且板上只有一个空格。