Точка гравитации
Вы практикуетесь в жонглировании с квадратными плитками, которые на вид одинаковы, но на самом деле бывают трех типов: A, B и X. Тип плитки определяется её массой. Все плитки одного типа имеют одинаковую массу. Масса плиток типа A находится в диапазоне [mA1, mA2]. Масса плиток типа B — в диапазоне [mB1, mB2]. Точные значения масс для типов A и B неизвестны. Масса плиток типа X точно равна mX.
Вы получили большой объект, состоящий из плиток, расположенных в сетке размером H×W. Плитки склеены друг с другом по краям, но некоторые ячейки в сетке могут быть пустыми.
Ваша задача — сбалансировать объект на шесте, что требует, чтобы центр тяжести объекта находился на плитке, а не на пустой ячейке. Центр тяжести каждой плитки находится в её центре. Центр тяжести всего объекта, состоящего из двух частей с массами m_1 и m_2, находится в точке, делящей отрезок между их центрами в отношении m_2:m_1.
Вам нужно написать программу, которая вычисляет вероятность того, что центр тяжести объекта находится на плитке, а не на пустой ячейке. Хотя точные массы плиток A и B неизвестны, они равномерно распределены в указанных диапазонах. Предполагается, что распределения для A и B независимы.
Входные данные
Входные данные имеют следующий формат.
H W
mA1 mA2 mB1 mB2 mX
M_{1,1}M_{1,2}…M_{1,W}
M_{2,1}M_{2,2}…M_{2,W}
...
M_{H,1}M_{H,2}…M_{H,W}
Первая строка содержит два целых числа H и W (1 ≤ H, W ≤ 50), разделенные пробелом, где H и W — количество строк и столбцов матрицы.
Вторая строка содержит пять целых чисел mA1, mA2, mB1, mB2 и mX (1 ≤ mA1 < mA2 ≤ 100, 1 ≤ mB1 < mB2 ≤ 100, 1 ≤ mX ≤ 100), разделенные пробелом.
Следующие H строк, каждая из которых состоит из W символов, представляют матрицу. Символы A, B и X обозначают плитки типов A, B и X соответственно, а . обозначает пустую ячейку. В этих строках нет других символов.
Для ячейки в i-й строке и j-м столбце координата левого верхнего угла — (i, j), а правого нижнего — (i+1, j+1).
Предполагается, что в матрице есть хотя бы одна плитка каждого типа A, B и X, и все плитки соединены хотя бы по одному краю. Также предполагается, что вероятность того, что x-координата центра тяжести объекта является целым числом, равна нулю, и то же самое для y-координаты.
Выходные данные
Выведите вероятность того, что центр тяжести объекта находится на плитке. Ошибка в выводе не должна превышать 10^{−8}.