이기는 수 찾기

4×4 틱택토는 위에서 아래로 0부터 3까지 번호를 매긴 네 개의 행과, 왼쪽에서 오른쪽으로 0부터 3까지 번호를 매긴 네 개의 열로 이루어진 판에서 진행한다. 두 플레이어 x와 o가 번갈아 두며, 항상 x가 먼저 둔다. 같은 행, 같은 열, 또는 주대각선 위에 자신의 말 네 개를 가장 먼저 놓는 사람이 이긴다. 판이 가득 찼는데도 어느 쪽도 한 줄을 완성하지 못했다면 무승부다.

지금은 x가 둘 차례다. x가 어떤 수를 두어서, 그 이후 o가 어떻게 두더라도 언젠가는 반드시 x가 이기도록 만들 수 있다면 x에게 강제 승리(필승)가 있다고 한다. 이는 바로 다음 수에 이겨야 한다는 뜻이 아니라(그럴 수도 있지만), o가 무엇을 두든 결국 승리를 보장하는 전략이 있다는 뜻이다.

x가 둘 차례인, 도중까지 진행된 게임이 주어졌을 때 x에게 강제 승리가 있는지 판정하라. 두 플레이어는 각각 이미 두 수 이상을 두었고, 아직 어느 쪽도 이기지 않았으며, 판은 가득 차 있지 않다고 가정해도 된다.

입력은 하나 이상의 테스트 케이스로 이루어지며, 입력의 끝은 $ 문자로 시작하는 줄로 표시된다. 각 테스트 케이스는 ? 하나만 있는 줄로 시작하고, 그 다음에 판을 나타내는 네 줄이 이어진다. 판을 나타내는 각 줄은 정확히 네 개의 문자로 이루어지며, 빈 칸을 뜻하는 마침표 ., 소문자 x, 소문자 o만 사용한다.

각 테스트 케이스마다 한 줄을 출력한다. x에게 강제 승리가 있으면 그 첫 번째 필승 수의 위치를 (행,열) 형식으로, 공백 없이 정확히 출력한다(예: (0,1)). 강제 승리가 없으면 대신 #####를 출력한다.

첫 번째 필승 수는 이기기까지 걸리는 수의 개수가 아니라 판 위의 위치로 정한다. 칸을 (0,0), (0,1), (0,2), (0,3), (1,0), (1,1), ..., (3,2), (3,3) 순서로 살펴보면서 가장 먼저 찾은 필승 수를 출력한다. 예를 들어 두 번째 예제 판(o... / .ox. / .xxx / xooo)에서 x는 (0,3)이나 (2,0)에 두면 곧바로 이길 수 있지만, (0,1)에 두어도 (승리가 늦어질 뿐) 여전히 승리가 보장되며, (0,1)이 탐색 순서에서 더 앞서므로 답은 (0,1)이다.