B - Faucets and Drains Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

ある水槽には N 個の蛇口 1,2,\dots,N と、M 個の排水管 1,2,\dots,M が付いています。 N 個の蛇口と M 個の排水管のうち、ちょうど 1 つが詰まっています。

o と x からなる長さ M の文字列 S_1,S_2,\dots,S_N が与えられます。 蛇口 i から水を注いだとき、排水管 j から水が出てくる(すなわち、蛇口 i と排水管 j がいずれも詰まっていない)ならば S_i の j 文字目は o であり、そうでないとき x です。

N 個の蛇口と M 個の排水管のうちどれが詰まっているかを特定してください。 ただし、答えがちょうど 1 つに特定できるような入力が与えられることは保証されます。

制約

  • 2 \leq N \leq 100
  • 2 \leq M \leq 100
  • N と M は整数
  • S_i は o と x からなる長さ M の文字列
  • 答えがちょうど 1 つに特定できる

入力

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

N M   
S_1  
S_2  
\vdots  
S_N  

出力

答えを 1 行で出力せよ。 詰まっているのが蛇口 i ならば Faucet と i を空白区切りで出力せよ。 詰まっているのが排水管 j ならば Drain と j を空白区切りで出力せよ。


入力例 1

3 4
oooo
xxxx
oooo

出力例 1

Faucet 2

蛇口 2 が詰まっています。


入力例 2

4 3
oxo
oxo
oxo
oxo

出力例 2

Drain 2

入力例 3

2 2
xo
xo

出力例 3

Drain 1

Score : 200 points

Problem Statement

A water tank has N faucets 1,2,\dots,N and M drains 1,2,\dots,M. Exactly one of the N faucets and M drains is clogged.

You are given N strings S_1,S_2,\dots,S_N, each of length M and consisting of o and x. The j-th character of S_i is o if water comes out of drain j when water is poured from faucet i (that is, neither faucet i nor drain j is clogged), and x otherwise.

Identify which of the N faucets and M drains is clogged. It is guaranteed that the answer can be uniquely determined from the input.

Constraints

  • 2 \leq N \leq 100
  • 2 \leq M \leq 100
  • N and M are integers.
  • S_i is a string of length M consisting of o and x.
  • The answer can be uniquely determined.

Input

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

N M   
S_1  
S_2  
\vdots  
S_N  

Output

Print the answer in one line. If faucet i is clogged, print Faucet and i separated by a space. If drain j is clogged, print Drain and j separated by a space.


Sample Input 1

3 4
oooo
xxxx
oooo

Sample Output 1

Faucet 2

Faucet 2 is clogged.


Sample Input 2

4 3
oxo
oxo
oxo
oxo

Sample Output 2

Drain 2

Sample Input 3

2 2
xo
xo

Sample Output 3

Drain 1