You have an egg carton that can be represented as a grid. The grid consists of 3 rows, numbered from 1 to 3, and columns, numbered from 1 to . The cell at row and column is denoted as . Each cell can be either usable or unusable; each usable cell can only hold at most 1 egg while unusable cells, as the name implies, cannot be used.
You want to put exactly eggs into usable cells of your carton such that the distance between any two closest eggs is maximized. The distance between an egg in cell and another egg in cell can be calculated using Euclidean distance, i.e. .
Determine the maximum possible distance between any two closest eggs, or determine if it is impossible to put eggs into your carton.
输入格式
Input begins with two integers (; ) representing the number of columns of your egg carton and the number of eggs. Each of the next 3 lines contains a string of length that consists of either character '.' or '#'. The character of string represents the condition of cell of the carton. Cell is usable if and unusable if .
输出格式
If eggs can be put into your carton, then output a real number in a single line representing the maximum possible distance between any two closest eggs. Your answer is considered correct if its absolute or relative error does not exceed .
If eggs cannot be put into your carton, then output in a single line.
样例
样例输入 1
5 2
#....
.....
....#
样例输出 1
4.472136
数据范围与提示
Explanation for the sample input/output #1
The maximum distance between any two closest eggs can only be achieved by putting the eggs in cells and , where the distance between the two (closest) eggs is .
