CF1689D.Lena and Matrix

Lena is a beautiful girl who likes logical puzzles.

As a gift for her birthday, Lena got a matrix puzzle!

The matrix consists of $n$ rows and $m$ columns, and each cell is either black or white. The coordinates $(i,j)$ denote the cell which belongs to the $i$-th row and $j$-th column for every $1\leq i \leq n$ and $1\leq j \leq m$. To solve the puzzle, Lena has to choose a cell that minimizes the Manhattan distance to the farthest black cell from the chosen cell.

More formally, let there be $k \ge 1$ black cells in the matrix with coordinates $(x_i,y_i)$ for every $1\leq i \leq k$. Lena should choose a cell $(a,b)$ that minimizes $$\max_{i=1}^{k}(|a-x_i|+|b-y_i|).$$

As Lena has no skill, she asked you for help. Will you tell her the optimal cell to choose?

莉娜是一位喜欢逻辑谜题的漂亮女孩。

作为生日礼物，莉娜收到了一个矩阵谜题！

该矩阵包含 $n$ 行和 $m$ 列，每个格子为黑色或白色。坐标 $(i,j)$ 表示第 $i$ 行、第 $j$ 列的格子（其中 $1\leq i \leq n$，$1\leq j \leq m$）。要解开这个谜题，莉娜需选择一个格子，使得它到最远的黑色格子的曼哈顿距离最小。

更准确地说，设矩阵中一共有 $k \ge 1$ 个黑色格子，其坐标为 $(x_i,y_i)$（$1\leq i \leq k$）。莉娜需选择一个格子 $(a,b)$，使得下式取最小值：

$$\max_{i=1}^{k}(|a-x_i|+|b-y_i|).$$

由于莉娜不擅长解题，她向你求助。你能告诉她应选择哪个最优格子吗？

There are several test cases in the input data. The first line contains a single integer $t$ ($1\leq t\leq 10\,000$) — the number of test cases. This is followed by the test cases description.

The first line of each test case contains two integers $n$ and $m$ ($2\leq n,m \leq 1000$) — the dimensions of the matrix.

The following $n$ lines contain $m$ characters each, each character is either 'W' or 'B'. The $j$-th character in the $i$-th of these lines is 'W' if the cell $(i,j)$ is white, and 'B' if the cell $(i,j)$ is black.

It is guaranteed that at least one black cell exists.

It is guaranteed that the sum of $n\cdot m$ does not exceed $10^6$.

输入数据包含多个测试用例。第一行包含一个整数 $t$（$1\leq t\leq 10\,000$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$2\leq n,m \leq 1000$），表示矩阵的维度。

接下来的 $n$ 行，每行包含 $m$ 个字符，每个字符为 'W' 或 'B'。在这些行中，第 $i$ 行的第 $j$ 个字符为 'W' 表示单元格 $(i,j)$ 是白色的，为 'B' 表示单元格 $(i,j)$ 是黑色的。

保证至少存在一个黑色单元格。

保证所有测试用例中 $n\cdot m$ 的总和不超过 $10^6$。

For each test case, output the optimal cell $(a,b)$ to choose. If multiple answers exist, output any.

对于每个测试用例，输出应选择的最优单元格 $(a,b)$。如果存在多个答案，输出任意一个即可。

In the first test case the two black cells have coordinates $(1,1)$ and $(3,2)$. The four optimal cells are $(1,2)$, $(2,1)$, $(2,2)$ and $(3,1)$. It can be shown that no other cell minimizes the maximum Manhattan distance to every black cell.

In the second test case it is optimal to choose the black cell $(2,2)$ with maximum Manhattan distance being $2$.

在第一个测试用例中，两个黑格的坐标分别为 $(1,1)$ 和 $(3,2)$。四个最优格子为 $(1,2)$、$(2,1)$、$(2,2)$ 和 $(3,1)$。可以证明，不存在其他格子能使到所有黑格的最大曼哈顿距离更小。

在第二个测试用例中，选择黑格 $(2,2)$ 是最优的，此时最大曼哈顿距离为 $2$。