M. Ha, It's Yesterday Five Times More（Hard Version）

The only difference between the easy version and the hard version is that, in the hard version, the range of T, n, m is larger. X and Y are not necessarily 1, and c is not necessarily 0 or 1000.

Background

2023 ICPC Nanjing Site, Problem A The picture is not related to the description of the problem. If you cannot understand Chinese, feel free to skip it.

Students from Nanjing Normal University participate in the 2023 ICPC Nanjing Site.

In 2018, 2020, 2021, 2022, and 2023, the SUA problem-setting team proposed five problems related to kangaroos in the ICPC Nanjing Site.

To warm up before the Jinan Site, pzr decided to solve the following problem about kangaroos. Can you help him?

Description

Given an $n \times m$ grid, initially, each cell can have at most one kangaroo (but during the operation, a cell may contain multiple kangaroos). In addition, there's a hole in a specific cell $(X, Y)$.

You can perform several operations, each of which is one of the following:

• Cost $c$, causing all kangaroos to gather with the hole as the center, specifically:
  • All kangaroos in the cells to the left of the hole (in the same row but with column number less than the column number of the hole) move one cell to the right.
  • All kangaroos in the cells to the right of the hole (in the same row but with column number greater than the column number of the hole) move one cell to the left.
  • All kangaroos in the cells above the hole (in the same column but with row number less than the row number of the hole) move one cell down.
  • All kangaroos in the cells below the hole (in the same column but with row number greater than the row number of the hole) move one cell up.
  • All kangaroos in the cells to the top-left of the hole (with row number less than the row number of the hole and column number less than the column number of the hole) move one cell to the right and then one cell down.
  • All kangaroos in the cells to the bottom-left of the hole (with row number greater than the row number of the hole and column number less than the column number of the hole) move one cell to the right and then one cell up.
  • All kangaroos in the cells to the top-right of the hole (with row number less than the row number of the hole and column number greater than the column number of the hole) move one cell to the left and then one cell down.
  • All kangaroos in the cells to the bottom-right of the hole (with row number greater than the row number of the hole and column number greater than the column number of the hole) move one cell to the left and then one cell up.
• Cost $1$, choosing a specific kangaroo.
  • Move it to one of the four adjacent cells (up, down, left, right).

When a kangaroo falls into the hole, it will be removed from the grid. If after a series of operations, exactly one kangaroo remains in the grid, it becomes the final winner.

Now, assuming you are a kangaroo at position $(i, j)$, please calculate: What is the minimum cost to become the final winner? For each kangaroo, find the answers $c_1, c_2, \ldots, c_k$. To avoid excessive output, you only need to find the sum of the squares of the individual answers, i.e., $\sum_{i=1}^k c_i^2$.

Input Format

The first line contains an integer $T$, representing the number of test cases.

For each test case:

The first line contains five integers $n, m, c, X, Y$, representing the number of rows and columns of the grid, the cost of the first operation, and the position of the hole.

Next, there are $n$ lines, each containing a string of length $m$, consisting of only $0$ or $1$, indicating the initial number of kangaroos in that cell. It's guaranteed that there are no kangaroos at the hole's initial position. It's guaranteed that there is at least one kangaroo in the entire grid.

Output Format

For each test case: Only one non-negative integer, representing the sum of the squares of the minimum costs for each kangaroo.

Sample Input 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

Sample Output 1

77
132
28
3642
90
26676

Sample 1 Explanation

For the first test case

The hole is located at (2,3).

0100

11x0

0110

For the kangaroo at (1,2), the operations are as follows:

• Move itself one cell to the left

1000

1100

0110

• All kangaroos gather towards the center

0000

0200

0000

Note that at this point, the kangaroo at (1,2) and the kangaroo at (1,1) will both be moved to (2,2).

• Move another kangaroo one cell to the right

0000

0100

0000

Therefore, the minimum cost is $4$.

Similarly, we can obtain the minimum cost for the kangaroo at (2,1) as $2$, at (2,2) as $4$, at (3,2) as $4$, and at (3,3) as $5$.

Hence, the output is $4^2+2^2+4^2+4^2+5^2=77$

Data Range and Constraints

---

Subtask 1 (10 points):

$T=1$

There is only one kangaroo in the entire grid.

---

Subtask 2 (20 points):

$n=3, m=4$

---

Subtask 3 (20 points):

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

It's guaranteed that the sum of $n \times m$ in all test cases does not exceed $5 \times 10^3$

---

Subtask 4 (20 points):

Kangaroos are only distributed to the left, right, above, or below the hole.

---

Subtask 5 (20 points):

$c=0$

---

Subtask 6 (10 points):

No special properties.

---

For all test cases:

$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$

It's guaranteed that there are no kangaroos initially at the hole's position. It's guaranteed that there is at least one kangaroo in the entire grid.

It's guaranteed that the sum of $n \times m$ in all test cases does not exceed $5 \times 10^6$.

It can be proved that under the current constraints, any kangaroo can become the final winner.

It can be proved that under the current constraints, the answer must be representable by a $64$-bit integer.

The English Version of the Statement is Translated By ChatGPT.