Точка тяжіння
Ви займаєтеся жонглюванням, використовуючи кілька квадратних плиток. Всі плитки однакові за розміром, але існує три різні типи: A, B та X. Тип плитки визначається її масою. Всі плитки одного типу мають однакову масу. Маса плиток типу A знаходиться в діапазоні [mA1, mA2]. Аналогічно, маса плиток типу B знаходиться в діапазоні [mB1, mB2]. Точні значення мас для типів A та B невідомі. Маса плиток типу X точно дорівнює mX.
Ви отримали великий об'єкт, що складається з плиток, розташованих у сітці розміром H×W. Всі сусідні плитки склеєні по краях. Деякі клітинки в сітці 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 символів, представляють матрицю. У цих H рядках A, B та X позначають плитки типу A, B та X відповідно, а . позначає порожню клітинку. Інших символів у цих H рядках немає.
Координати лівого верхнього кута клітинки у i-му рядку та j-му стовпці — це (i, j), а координати правого нижнього кута — (i+1, j+1).
Ви можете припустити, що в матриці є принаймні одна плитка кожного типу A, B та X, і всі плитки з'єднані принаймні по одному краю. Також можна припустити, що ймовірність того, що x-координата центру ваги об'єкта є цілим числом, дорівнює нулю, і ймовірність того, що y-координата центру ваги об'єкта є цілим числом, дорівнює нулю.
Вихідні дані
Виведіть ймовірність того, що центр ваги об'єкта знаходиться на плитці. Вихід не повинен містити помилку більше ніж 10^{−8}.