题目背景

由于洛谷评测机太慢，$3s\to 4s$。

题目描述

S 是学校里屈指可数的理工天才。两脚分离式的电动平衡车，通过刺激人体上臂、腰部及大腿的运动神经实现控制身体运动的电极装置，以及可以用无人机吊起来的巨幅轻薄柔性屏，只不过是 S 登峰造极的技术水平的冰山一角。这一次，S 又将目光投向了最近很流行的大语言模型（Large Language Model）。

大语言模型是机器学习中的新兴方向，其特点是使用大量的语料来训练语言模型，而正是算法的发展及算力的提升使得训练大语言模型不再捉襟见肘。此外，部分最新的大语言模型不仅支持文本输入输出，更支持音频、图像、视频等格式的多模态输入输出。但是 S 发现，即便是多模态的大语言模型，也不能正确处理一类特殊的图片——随机点立体图（Random Dot Stereogram）。

立体图是使用视错觉造成立体感知的图像，而随机点立体图的原理是通过对随机生成的位图进行平移变换，产生立体视觉。下图是一张简单的随机点立体图。通过将绿色虚线框中的部分向左平移 $2$ 个像素，可以产生虚线框中的部分浮在原图像之上的效果。注意除虚线框及左图中虚线框左侧的红色矩形，右图中虚线框右侧的绿色矩形覆盖的部分之外，图像的外围部分需要保持完全相同，而红色矩形及绿色矩形覆盖的区域则可以分别随机生成。形式化地，如果记左图为 $W$，右图为 $Y$，则将 $W$ 中第 $r_1$ 至 $r_2$ 行，第 $c_1$ 至 $c_2$ 列的矩形子区域平移至 $Y$ 中第 $r_1$ 至 $r_2$ 行，第 $c_1'$ 至 $c_2'$ 列时，需要满足 $r_1\le r_2$，$c_2 - c_1 = c_2'-c_1'\ge 0$ （为 $0$ 时恰好只移动一列），$c_1>c_1'$；只有 $W$ 中的第 $r_1$ 至 $r_2$ 行，第 $c_1'$ 至 $(c_1-1)$ 列及 $Y$ 中的第 $r_1$ 至 $r_2$ 行，第 $(c_2'+1)$ 至 $c_2$ 列部分的像素都可以独立随机生成，无论平移前后矩形区域是否重叠。

S 发现：尽管大语言模型可以识别传统的图像验证码，但是如果使用随机点立体图来生成验证码，那么大语言模型将无法正确识别！为了验证这一发现，S 需要生成不同的随机点立体图来测试大语言模型是否能够识别图像内容。作为计划的第一步，S 想先测试大语言模型能否看出图片中的矩形。具体而言，S 将把两个可以表示为 $01$ 矩阵的 $N$ 行 $M$ 列的位图 $W$ 和 $Y$ 输入到大语言模型中，并询问 $Y$ 是否可以由 $W$ 向左平移某个矩形子区域得到。假设在平移前后，这一矩形子区域都不超出原图片的边界。为了检验大语言模型的输出，S 需要一个程序来计算，对于所有可能的平移距离，右半边的图片 $Y$ 是否可以通过对左半边的图片 $W$ 平移某个矩形子区域得到，并在可行时求出该矩形子区域的最大面积。由于 S 这周末还要陪 M 逛街，所以她想请你帮她实现一下这个程序。

输入格式

输入的第一行包含两个正整数 $N, M$，表示两个像素矩阵的行数和列数。保证 $1\le N, M\le 500$。

接下来 $N$ 行，每行输入一个包含 $M$ 个字符的字符串，表示 $W$ 的每一行。保证每个字符均为 0 或 1。

接下来 $N$ 行，每行输入一个包含 $M$ 个字符的字符串，表示 $Y$ 的每一行。保证每个字符均为 0 或 1。

输出格式

输出共一行，包含 $(m-1)$ 个由单个空格分隔开的整数，其中第 $i$（$1\le i \le m - 1$）个整数表示当平移距离为 $i$ 个像素时，可能的矩形子区域的最大面积。如果不存在任何满足要求的矩形子区域，则对这个移动距离输出 -1。

4 4
0100
0110
1001
1000
0100
1100
0011
0000

9 4 -1

11 11
01010100100
10111011000
10001010110
11011101110
10110010010
00100010010
11011010011
01001111001
00111000111
10010011101
00101110110
01010100100
10111011000
10001010110
11110111010
10001000010
00001001110
11101000111
01111100101
00111000111
10010011101
00101110110

-1 25 -1 -1 -1 -1 -1 -1 -1 -1

提示

样例解释 1

当固定平移距离为 $1$ 时，可能的最大矩形子区域在 $W$ 中对应第 $2$ 行至第 $4$ 行，第 $2$ 列至第 $4$ 列的矩形区域，其平移后在 $Y$ 中为第 $2$ 行至第 $4$ 行，第 $1$ 列至第 $3$ 列。

如果假设平移距离为 $2$，则可能的最大矩形子区域为 $W$ 中第 $3$ 列整列对应的矩形区域。

可以证明，不存在任何平移距离为 $3$ 的平移方法。

样例解释 2

该样例即为题面所附图片。

数据范围

对于所有数据，保证 $1\le N, M\le 500$，输入的 $W$ 和 $Y$ 是 $N$ 行 $M$ 列仅含 0 和 1 的字符矩阵。

题目来源

来自 2025 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2025）初赛。

题解等资源可在 https://gitlink.org.cn/thusaa/thupc2025pre/tree/master 查看。