Time Limit: 30000 MS    Memory Limit: 262144 K 


Description

scu07t01: windy7926778 fgjlwj wqb0039 三人被困在迷宫中,迷宫由n*m的格子组成,格子可能含有障碍物,三个人初始位置没有障碍物 在迷宫中,他们可以向上,向下,向左,向右四个方向走动,只能走到没有障碍物的格子 请问最少需要去掉多少格障碍物,可以使得三人两两之间可达

Input

输入包含多组测试数据,每组数据第一行为两个整数n和m ( 2 <= n,m <= 1000 ) 接下来n行,每行m个字符 其中 'w'代表windy的位置 'f'代表fgjlwj的位置 'W'代表wqb的位置 '.'代表没有障碍物的格子 '#'代表有障碍物的格子

Output

每组数据输出一行,为答案

Sample Input

4 4 w... #### .##f W##. 4 4 w.## #### .##f W##. 3 4 w##. #W## .##f 3 3 #w# ### W#f

Sample Output

2 3 3 2

Author

windy7926778