四子棋

Time Limit: 5000 ms Memory Limit: 262144 KiB

Problem Description

四子棋的棋盘有四行四列(行号03,列号03),玩家x和玩家o交替落子,首先将四子连成一条直线的玩家获胜。x先下子,问x是否有必胜策略。

Input

 
测试数据有T组(1T10)。每组测试数据的第一行是单个字符?(英文问号),接下来的四行表示4*4的棋盘,棋盘由字符(x)、(o)、(.)组成(小写字母x、小写字母o、小数点),分别表示xo的棋子与空位置。最后一行为单个字符@表示所有测试数据结束。

Output

 

输出T行,如果x有必胜策略输出(i,j),否则输出####。如果有多个必胜策略,输出满足i最小条件下j最小的必胜步(i,j)

Sample Input

?
....
.xo.
.ox.
....
?
o...
.ox.
.xxx
xooo
$

Sample Output

#####
(0,1)

Hint

 

1组测试数据:x下一步无论走哪里,o都有策略和x打平(棋盘下满无人胜则打平)。

2组测试数据:x下一步走(0,1)或者(0,3)或者(2,0)都必胜,走(0,1)虽然推迟了获胜,但编号是最小的。

Source

青岛理工交流赛