#P18200. Shift Puzzle

Shift Puzzle

Shift Puzzle

有两个 N×NN\times N 的网格 S,TS,T,每个格子为黑色或白色。用字符 # 表示黑色,用字符 . 表示白色。记 Sx,yS_{x,y} 为 SS 从上往下第 xx 行、从左往右第 yy 列的格子,TT 的记号相同。

你可以对网格 SS 进行以下操作:

选择整数 t,xt,x,满足 1≤t≤21\le t\le2、1≤x≤N1\le x\le N。

  • 若 t=1t=1,将第 xx 行向右循环移动一格,即同时将 Sx,1Sx,2…Sx,NS_{x,1}S_{x,2}\ldots S_{x,N} 替换为 Sx,NSx,1…Sx,N−1S_{x,N}S_{x,1}\ldots S_{x,N-1}。
  • 若 t=2t=2,将第 xx 列向下循环移动一格,即同时将 S1,xS2,x…SN,xS_{1,x}S_{2,x}\ldots S_{N,x} 替换为 SN,xS1,x…SN−1,xS_{N,x}S_{1,x}\ldots S_{N-1,x}。

判断能否在至多 N3N^3 次操作内将 SS 变为 TT。若可以,输出任意一个满足操作次数限制的方案。

输入格式

第一行包含一个整数 NN,满足 2≤N≤802\le N\le80。

接下来 NN 行,每行一个长度为 NN 的字符串,表示网格 SS。

再接下来 NN 行,每行一个长度为 NN 的字符串,表示网格 TT。

每个字符串只包含 # 和 .。

输出格式

如果无法在 N3N^3 次操作以内将两个网格变为相同,输出一行 No。

否则,第一行输出 Yes,第二行输出操作次数 MM,满足 0≤M≤N30\le M\le N^3。

接下来 MM 行,每行输出两个整数 t,xt,x,依次表示该次操作选择的类型和行号或列号,满足 1≤t≤21\le t\le2、1≤x≤N1\le x\le N。

样例 1

输入:

3
.#.
#.#
.#.
#.#
...
#.#

输出:

Yes
4
1 3
2 3
2 1
1 1

执行样例方案后,网格的变化如下。红框标出了下一次操作所选择的行或列。

样例1的四次循环移位

样例 2

输入:

3
.#.
#.#
.#.
.#.
#.#
.#.

输出:

Yes
0

样例 3

输入:

13
.............
....#####....
......#......
......#......
......#......
......#......
.............
....#...#....
....#...#....
....#...#....
....#...#....
.....###.....
.............
....####.....
....#...#....
....####.....
....#........
....#........
.............
.....###.....
....#...#....
....#........
....#...#....
.....###.....
.............
.............

输出:

No