M. 哈！昨日五次重现（困难版）

简单版和困难版的唯一区别是，在困难版中，$T,n,m$ 的范围更大，$X,Y$ 不一定是 $1$，$c$ 不一定是 $0$ 或 $1000$。

题目背景

2023 ICPC 南京站 A 题

南师学子参加 2023 ICPC南京站

在 2018、2020、2021、2022、2023 年的 ICPC 南京站中， SUA 命题组提出了五道与袋鼠相关的题目。

为了在济南站前热身， pzr 决定解决以下袋鼠谜题，你能帮帮他吗？

题目描述

给定一张 $n \times m$ 的网格，初始情况下，每个格子中有至多一只袋鼠（但是操作过程中，格子中可以容纳多个袋鼠）。除此之外，某一个特定格子 $(X, Y)$ 上将有一个洞。

接下来，你可以执行若干操作，每种操作是如下之一：

• 花费 $c$ 的代价，使得所有袋鼠 以洞的位置为中心 聚集，具体来说：
  • 位于洞正左方的格子中（位于同一行，但是列号小于洞所在列号）的所有袋鼠向右移动一格。
  • 位于洞正右方的格子中（位于同一行，但是列号大于洞所在列号）的所有袋鼠向左移动一格。
  • 位于洞正上方的格子中（位于同一列，但是行号小于洞所在行号）的所有袋鼠向下移动一格。
  • 位于洞正下方的格子中（位于同一列，但是行号大于洞所在行号）的所有袋鼠向上移动一格。
  • 位于洞左上方的格子中（行号小于洞所在行号，列号小于洞所在列号）的所有袋鼠向右移动一格、再向下移动一格。
  • 位于洞左下方的格子中（行号大于洞所在行号，列号小于洞所在列号）的所有袋鼠向右移动一格、再向上移动一格。
  • 位于洞右上方的格子中（行号小于洞所在行号，列号大于洞所在列号）的所有袋鼠向左移动一格、再向下移动一格。
  • 位于洞右下方的格子中（行号大于洞所在行号，列号大于洞所在列号）的所有袋鼠向左移动一格、再向上移动一格。
• 花费 $1$ 的代价，选择一只特定的袋鼠。
  • 将其移动到相邻（上、下、左、右）的四个格子之一。

当一只袋鼠掉入洞中，它将在网格中移除。如果在一系列操作后，恰有一只袋鼠留在网格中，则它成为最终赢家。

现在，假设你是某个位置 $(i, j)$ 的袋鼠，请你计算：至少需要花费多少代价，才能成为最终赢家？请对于每只袋鼠，求出答案 $c_1,c_2,\cdots ,c_k$。为了避免大量输出，你只需要求出各个答案的平方和，即 $\sum_{i=1}^k c_i^2$ 。

输入格式

第一行一个整数 $T$，表示测试数据组数。

接下来对于每组数据：

第一行五个整数 $n, m, c, X, Y$，分别表示网格的行数和列数，第一种操作的代价，以及洞所在位置。

接下来 $n$ 行每行一个长为 $m$ 的字符串，仅包含 $0$ 或 $1$，表示初始该格子中的袋鼠数量。保证洞所在位置一开始没有袋鼠。保证网格中至少有一只袋鼠。

输出格式

对于每组数据，仅一个非负整数，表示对于各袋鼠而言的最小代价的平方和。

样例输入1

6
3 4 2 2 3
0100
1100
0110
3 4 2 2 3
1000
1101
0100
3 4 1 2 3
0100
1100
0100
3 4 100 2 3
1111
1101
1111
3 4 0 2 3
1111
1101
1111
7 10 5 3 6
1111110110
1010110010
0110101100
1100100110
1110010010
1010100100
0100110110

样例输出1

77
132
28
3642
90
26676

样例1解释

对于第一组测试点

洞的位置为（2,3）。

0100

11x0

0110

对于（1,2）处的袋鼠，操作如下：

• 自身左移一格

1000

1100

0110

• 所有袋鼠，向中心聚集

0000

0200

0000

注意，此时（1,2）处的袋鼠和（1,1）处的袋鼠都将被移动到（2,2）

• 使另一只袋鼠，右移一格。

0000

0100

0000

那么，最小代价是 $4$。

同理，可以得到（2,1）处的最小代价为 $2$，$(2,2)$ 处的最小代价是 $4$，$(3,2)$ 处的最小代价为 $4$，$(3,3)$ 处的最小代价为 $5$。

因此，输出 $4^2+2^2+4^2+4^2+5^2=77$

数据范围与约定

---

子任务 1（10分）：

$T=1$

地图上只有一只袋鼠。

---

子任务 2（20 分）：

$n=3,m=4$

---

子任务 3 （20 分）：

$3\le n,m\le 50, n + m > 6$

保证所有数据中 $n\times m$ 的和不超过 $5\times 10^3$

---

子任务 4（20 分）：

袋鼠仅可能分布在洞的正左方、正右方、正上方或正下方。

---

子任务 5 （20 分）：

$c=0$

---

子任务 6（10 分）：

无特殊性质

---

对于所有测试点：

$1\le T\le 10^5$

$3\le n,m\le 10^3$，$n+m>6$。

$0\le c\le 10^3$，$1\le X\le n$，$1\le Y\le m$

保证洞所在位置一开始没有袋鼠。保证整个网格中至少有一只袋鼠。

保证所有数据中 $n\times m$ 的和不超过 $5\times 10^6$。

可以证明，在现有的数据范围约定下，无论是哪一只袋鼠，都有可能成为最终赢家。

可以证明，在现有的数据范围约定下，答案一定在 $64$ 位整数可表示的范围内。