408962: GYM103389 F 地图压缩

你正在参与一款2D游戏的地图绘制，你拥有的美术素材是一张 $$$n\times n$$$ 的像素图片，从上到下依次编号为第 $$$1$$$ 行到第 $$$n$$$ 行，从左往右依次编号为第 $$$1$$$ 列到第 $$$n$$$ 列，其中第 $$$i$$$ 行第 $$$j$$$ 列的像素坐标为 $$$(i,j)$$$，它的内容可以用一个小写字母 $$$p_{i,j}$$$ 来表示。

你希望从这张素材中裁剪出一个连续的矩形区域作为游戏的地图。你进行了 $$$q$$$ 次尝试，每次尝试中你将会选择以 $$$(x_1,y_1)$$$ 为左上角、$$$(x_2,y_2)$$$ 为右下角的矩形部分（包括端点）作为游戏的地图。通过不断地尝试，你发现可以通过应用"四方连续"的方法来压缩地图。"四方连续纹样"是指一个单位矩形纹样向上下左右四个方向反复连续循环排列所产生的纹样，例如样例中以 $$$(1,1)$$$ 和 $$$(3,7)$$$ 为对角线端点的矩形可以看作以 $$$(1,1)$$$ 和 $$$(2,3)$$$ 为对角线端点的矩形向上下左右四个方向反复连续循环排列所产生的，该矩形包含 $$$2\times 3=6$$$ 个像素点。注意，纹样在生成地图的过程中可以超出边缘，超出边缘的部分将被忽略。

请写一个程序，对于每次尝试的地图，找到包含像素点数量最少的单位矩形纹样，使得它利用四方连续可以生成该次尝试的地图。

第一行包含两个正整数 $$$n$$$ 和 $$$q$$$ ($$$1\leq n\leq 2\,000$$$, $$$1\leq q\leq 10\,000$$$)，分别表示素材的尺寸和尝试的次数。

接下来 $$$n$$$ 行，第 $$$i$$$ 行包含一个长度为 $$$n$$$ 的小写字符串，其中第 $$$j$$$ 个字符表示 $$$p_{i,j}$$$。

接下来 $$$q$$$ 行，每行四个正整数$$$x_1,y_1,x_2,y_2$$$ ($$$1\leq x_1\leq x_2\leq n$$$, $$$1\leq y_1\leq y_2\leq n$$$)，依次表示每次尝试的矩形的对角线的端点坐标。

输出 $$$q$$$ 行，第 $$$i$$$ 行输出一个正整数，表示第 $$$i$$$ 次尝试对应的最小单位纹样包含的像素点数量。

8 5
abcabcab
defdefdb
abcabcab
aaaaaaaa
bbbbbbbb
cccccccc
bbbbbbbb
cccccccc
1 1 3 7
1 2 3 8
4 1 8 8
5 2 7 6
5 5 8 7

6
14
5
2
2