描述

Gazillion Games 公司的设计师们推出了一款新的简易游戏《 stake your claim 》。两名玩家（0号和1号）首先选择两个值$n$和$m$，然后创建一个$n \times n$的棋盘，其中随机放置$m$个0和$m$个1。从玩家0开始，双方轮流在空格（.）中放置自己的数字。当棋盘填满后，每位玩家的得分等于其数字的最大连通区域的大小（连通区域定义为：区域内任意两点可通过仅北/南/东/西方向的移动路径连接）。得分最高的玩家获胜，并获得自己与对手得分的差值。两个完成游戏的示例如图所示（每方的最大连通区域用轮廓标出）。注意第二个示例中，两个包含2个0的区域并不连通。
为了测试游戏的平衡性，公司聘请你编写一个程序，给定任意初始棋盘状态，确定当前玩家的最佳落子位置，即能最大化玩家得分（或最小化对手得分）的位置。

输入

输入包含多个测试用例。每个测试用例以一个正整数$n$（$n \leq 8$）开始，表示棋盘大小。接下来$n$行描述棋盘的当前状态（从第0行开始），每行包含$n$个字符，取值为'0'、'1'或'.'（.表示空格）。输入保证：

• 棋盘上0的数量等于或比1多一个；
• 空格数量在1到10之间（含）。
  最后一个测试用例后以一行0结束输入，该行无需处理。

输出

对每个测试用例，输出一行，包含两个内容：当前玩家的最佳落子坐标，以及该落子能实现的最佳得分差值。若存在多个最优解，按字典序优先输出坐标最小的解。坐标格式如示例所示。

输入示例1

4  
01.1  
00..  
.01.  
...1  
4  
0.01  
0.01  
1..0  
.1..  
0  

输出示例1

(1,2) 2  
(2,2) -1  

来源

East Central North America 2006