{-# LANGUAGE BangPatterns #-} {-# LANGUAGE BinaryLiterals #-} {-# LANGUAGE MultiWayIf #-} {-# LANGUAGE NumDecimals #-} {-# LANGUAGE ScopedTypeVariables #-} {-# LANGUAGE TupleSections #-} {-# LANGUAGE FlexibleContexts #-} {-# OPTIONS_GHC -O2 #-} {-# OPTIONS_GHC -Wno-tabs #-} import Control.Applicative import Control.Arrow import Control.Monad import Control.Monad.ST import Data.Char import Data.List import Data.Maybe import qualified Data.ByteString.Char8 as B import Data.Array import Data.Array.ST.Safe import Data.STRef import Debug.Trace import Text.Printf readInt = readLn :: IO Int readInteger = readLn :: IO Integer readInts = map ( fst . fromJust . B.readInt ) . B.words <$> B.getLine readIntegers = map ( fst . fromJust . B.readInteger ) . B.words <$> B.getLine which a b f = if f then a else b mp [ a, b ] = ( a, b ) modifyArray a i f = writeArray a i =<< f <$> readArray a i printList [] = putChar '\n' printList [a] = print a printList (a:as) = putStr ( show a ) >> putChar ' ' >> printList as main = do [ h, w ] <- readInts [ ss, ts ] <- replicateM 2 $ replicateM h getLine let es :: Maybe [Double] = case ( match ss ts, match ( rev ss ) ts ) of ( True, True ) -> Just $ f 1 [ 0 .. ] ( True, False ) -> Just $ f 1 [ 0, 2 .. ] ( False, True ) -> Just $ f 1 [ 1, 3 .. ] ( False, False ) -> Nothing case es of Just es -> printf "%.12f\n" $ sum $ take 100000 es otherwise -> print (-1) rev = reverse . map reverse match ss ts = and $ zipWith match' ss ts where match' s t = and $ zipWith (/=) s t f _ [] = [] f p (i:is) = ( i + 1 ) * p * p' : f ( p * ( 1 - p' ) ) is where p' = 1 - ( 2 ** (-i) )