import Data.Bool import Data.List import qualified Data.IntMap as M import qualified Data.IntSet as S unionMap f s = S.foldr (\e acc -> S.union acc (f e)) S.empty s main = do [w,h] <- map read . words <$> getLine ms <- map read . words <$> getContents :: IO [Int] putStrLn (bool "impossible" "possible" (anyClosed w h ms)) anyClosed w h ms = or (unfoldr (dfs w) ims) where ims = M.fromDistinctAscList (zip [i | i<-[1..(w+1)*h], mod i (w+1) /= 0] ms) dfs w ims | M.null ims = Nothing | otherwise = Just (isClosed w [i,i] (M.keysSet ims'), M.difference ims ims') where (i,m) = head (M.toList ims) ims' = reachable w m ims (S.singleton i) (S.singleton i) reachable w m ims acc b | S.null b = M.filterWithKey (\k _ -> S.member k acc) ims | otherwise = reachable w m ims (S.union acc b') (S.difference b' acc) where b' = unionMap (\i -> S.fromList (filter movable [i-1,i+1,i-(w+1),i+(w+1)])) b movable k = M.findWithDefault 0 k ims == m isClosed w acc@(a:a':as) is | S.null is = False | not (S.member a is) = False | elem a as = True | otherwise = or (map (\i -> isClosed w (i:acc) is) (delete a' [a-1,a+1,a-(w+1),a+(w+1)]))