B - Rectangle Detection Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200 点

問題文

高橋くんは、以下の方法で 10 個の文字列 S_1,S_2,\dots,S_{10} を生成しました。

  • まず、 S_i (1 \le i \le 10)= .......... ( . が 10 個並んだ文字列) とする。
  • 次に、以下の条件を全て満たす 4 つの整数 A,B,C,D を選ぶ。
    • 1 \le A \le B \le 10
    • 1 \le C \le D \le 10
  • その後、以下の条件を全て満たす全ての整数組 (i,j) について、 S_i の j 文字目を # に書き換える。
    • A \le i \le B
    • C \le j \le D

以上の方法で生成された S_1,S_2,\dots,S_{10} が与えられるので、高橋くんが選んだ整数 A,B,C,D を求めてください。
なお、制約より A,B,C,D は一意に定まる (答えはただひとつ存在する) ことが証明できます。

制約

  • S_1,S_2,\dots,S_{10} は問題文中の方法で生成されうるそれぞれ長さ 10 の文字列

入力

入力は以下の形式で標準入力から与えられる。

S_1
S_2
\vdots
S_{10}

出力

答えを以下の形式で出力せよ。

A B
C D

入力例 1

..........
..........
..........
..........
...######.
...######.
...######.
...######.
..........
..........

出力例 1

5 8
4 9

高橋くんが選んだ整数は A=5,B=8,C=4,D=9 です。
このように選ぶことにより、 S_5,S_6,S_7,S_8 の 4 文字目から 9 文字目が # であり他の文字が . である 10 個の長さ 10 の文字列 S_1,S_2,\dots,S_{10} が生成されます。
これは入力で与えられた 10 個の文字列と一致します。

入力例 2

..........
..#.......
..........
..........
..........
..........
..........
..........
..........
..........

出力例 2

2 2
3 3

入力例 3

##########
##########
##########
##########
##########
##########
##########
##########
##########
##########

出力例 3

1 10
1 10

Score : 200 points

Problem Statement

Takahashi generated 10 strings S_1,S_2,\dots,S_{10} as follows.

  • First, let S_i (1 \le i \le 10)= .......... (10 .s in a row).
  • Next, choose four integers A, B, C, and D satisfying all of the following.
    • 1 \le A \le B \le 10.
    • 1 \le C \le D \le 10.
  • Then, for every pair of integers (i,j) satisfying all of the following, replace the j-th character of S_i with #.
    • A \le i \le B.
    • C \le j \le D.

You are given S_1,S_2,\dots,S_{10} generated as above. Find the integers A, B, C, and D Takahashi chose.
It can be proved that such integers A, B, C, and D uniquely exist (there is just one answer) under the Constraints.

Constraints

  • S_1,S_2,\dots,S_{10} are strings, each of length 10, that can be generated according to the Problem Statement.

Input

The input is given from Standard Input in the following format:

S_1
S_2
\vdots
S_{10}

Output

Print the answer in the following format:

A B
C D

Sample Input 1

..........
..........
..........
..........
...######.
...######.
...######.
...######.
..........
..........

Sample Output 1

5 8
4 9

Here, Takahashi chose A=5, B=8, C=4, D=9.
This choice generates 10 strings S_1,S_2,\dots,S_{10}, each of length 10, where the 4-th through 9-th characters of S_5,S_6,S_7,S_8 are #, and the other characters are ..
These are equal to the strings given in the input.

Sample Input 2

..........
..#.......
..........
..........
..........
..........
..........
..........
..........
..........

Sample Output 2

2 2
3 3

Sample Input 3

##########
##########
##########
##########
##########
##########
##########
##########
##########
##########

Sample Output 3

1 10
1 10