Wall Value

Albert enjoys a board game that can be played alone. To play, he first prepares a grid board with $R$ rows and $C$ columns and places walls on some cells. Then he puts $N$ game pieces, one each, on $N$ different empty cells (cells without a wall). Last, he picks one of the remaining empty cells as the destination for every piece. Let the destination be $(r, c)$ (row $r$, column $c$). The pieces are numbered 1 to $N$, and the cell where piece $i$ is placed is $(X_i, Y_i)$.

For example, the left figure below shows a board with $R = C = 4$, where the cells marked 'W' are walls and the cells marked '.' are empty. Let $A_i$ be the string of length $C$ that shows row $i$ of the board. The board in this example is $A = [".WW.", "..W.", ".WW.", "...."]$. The right figure shows the cells where Albert placed three pieces and the destination, with $X = [1, 1, 4]$, $Y = [1, 4, 4]$, and $(r, c) = (2, 2)$.

Each piece moves up, down, left, or right through empty cells to reach the destination. Let $d_i$ be the minimum distance piece $i$ must travel to reach the destination. In the example above, $d_1 = 2$ (move down, then right), $d_2 = 9$, and $d_3 = 6$. Let $D = \sum_{1 \le i \le N} d_i$ be the total minimum distance of all pieces. This is the score of the game. The score of this example is $2 + 9 + 6 = 17$.

Albert wants to change the game a little. First, he keeps the initial board state and removes exactly one wall. Removing a wall can open new paths, so the score stays the same or gets lower. Call the drop in score the value of the removed wall. The example board has 5 walls, so Albert can remove one wall in 5 different ways. The 'X' marks in the figure show the removed walls. They are empty cells now, so pieces can pass through them.

For the five new boards, compute the score and subtract it from the original score of 17 to get the value of the removed wall. From left to right:

• In the leftmost game, the score is 17, the same as the original, so the wall at (1, 2) has value 0.
• In the second game, the score is also 17, and the wall at (1, 3) has value 0.
• In the third game, the score is 9, because the minimum distances of pieces 2 and 3 drop to $d_2 = 3$ and $d_3 = 4$. So the wall at (2, 3) has value 8.
• In the fourth game, the score is 13, because the minimum distances of pieces 2 and 3 drop to $d_2 = 7$ and $d_3 = 4$. So the wall at (3, 2) has value 4.
• In the fifth game, the score is 17, so the wall at (3, 3) has value 0.

Adding the values of all five walls gives $0 + 0 + 8 + 4 + 0 = 12$. Call this the total wall value.

Given the board, find the original score $D$ and the total wall value.

The first line contains the number of test cases $T$.

The first line of each test case contains $R$, $C$, $N$, $r$, and $c$, separated by spaces. The next $N$ lines each contain two integers $X_i$ and $Y_i$, separated by a space, which are the position of the $i$-th piece. The next $R$ lines each contain a string of length $C$ with no spaces, which is row $i$ of the board $A_i$. A wall is 'W' and an empty cell is '.'.

For each test case, print two integers separated by a space on one line. The first integer is the original score $D$. The second integer is the total wall value.

• $1 \le T \le 5$
• $2 \le R, C \le 200$
• $1 \le N \le 50$
• $1 \le r \le R$ and $1 \le c \le C$
• For each $i$ with $1 \le i \le N$:
  • $1 \le X_i \le R$ and $1 \le Y_i \le C$
• Within each test case, the piece positions and the destination are distinct. No two pieces share a cell, and no piece shares a cell with the destination.
• Every piece position and the destination are empty cells (no wall).
• Input only includes test cases where, with no walls removed, every piece can reach the destination through empty cells moving up, down, left, or right.
• There is at least 1 wall.