莉娜是一个喜欢逻辑谜题的美丽女孩。
作为生日礼物,莉娜得到了一个矩阵拼图!
矩阵由 $$$n$$$ 行和 $$$m$$$ 列组成,每个单元格为黑色或白色。坐标 $$$(i,j)$$$ 表示每个 $$$1\leq i \leq n$$$ 和 $$$1\leq j \leq m$$$ 属于第 $$$i$$$ 行和 $$$j$$$ 列的单元格。为了解决这个难题,莉娜必须选择一个单元格,该单元格能够最小化与所选单元格最远的黑色单元格的曼哈顿距离。
更正式地说,对于每个 $$$1\leq i \leq k$$$,矩阵中有 $$$k \ge 1$$$ 个黑色单元,坐标为 $$$(x_i,y_i)$$$。 Lena 应该选择一个单元格 $$$(a,b)$$$ 来最小化 $$$$$$\max_{i=1}^{k}(|a-x_i|+|b-y_i|)。$$$$$$
由于莉娜没有技能,她向你求助。你会告诉她选择最佳的细胞吗?
输入
输入数据中有多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1\leq t\leq 10\,000$$$) - 测试用例的数量。接下来是测试用例描述。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2\leq n,m \leq 1000$$$) — 矩阵的维度。
以下 $$$n$$$ 行每行包含 $$$m$$$ 个字符,每个字符要么是“W”,要么是“B”。如果单元格 $$$(i,j)$$$ 为白色,则这些行中第 $$$i$$$ 中的第 $$$j$$$ 字符为“W”;如果单元格 $$$(i,j)$$$ 为黑色,则第 $$$j$$$ 字符为“B”。
保证至少存在一个黑色单元格。
保证$$$n\cdot m$$$之和不超过$$$10^6$$$。
输出
对于每个测试用例,输出最佳单元格 $$$(a,b)$$$ 进行选择。如果存在多个答案,则输出任何一个。
示例
输入 #1
5 3 2 BW WW WB 3 3 WWB WBW BWW 2 3 BBB BBB 5 5 BWBWB WBWBW BWBWB WBWBW BWBWB 9 9 WWWWWWWWW WWWWWWWWW BWWWWWWWW WWWWWWWWW WWWWBWWWW WWWWWWWWW WWWWWWWWW WWWWWWWWW WWWWWWWWB
输出 #1
2 1 2 2 1 2 3 3 6 5
注意
在第一个测试用例中,两个黑色单元格的坐标为 $$$(1,1)$$$ 和 $$$(3,2)$$$。四个最佳单元格是 $$$(1,2)$$$、$$$(2,1)$$$、$$$(2,2)$$$ 和 $$$(3,1)$$$。可以证明,没有其他单元可以最小化到每个黑色单元的最大曼哈顿距离。
在第二个测试用例中,最佳选择是黑色单元格 $$$(2,2)$$$,最大曼哈顿距离为 $$$2$$$。