-- Jonathan Frech, 2022-09-03
import Control.Exception (IOException,try)
import Data.List (delete,elemIndex,nub,sortOn)
import Data.Tuple (swap)
import Text.Read (readMaybe)
-- a partial ordering relation
type Rel a = [(a,a)]
type Vertices a = [a]
type Edges a = [(a,a)]
type Digraph a = (Vertices a, Edges a)
-- construct one possible total order compatible with the partial ordering
-- given, provided its induced graph does not contain directed cycles
total :: Eq a => Rel a -> [a]
total rel = order rel . nub . flatten $ rel where
order _ [] = []
order rel xs = let m = minimal (xs,rel)
in (m :) . uncurry (flip order) $ pluck m (xs,rel)
-- subgraph after plucking `v`
pluck :: Eq a => a -> Digraph a -> Digraph a
pluck v (vs,es) = (delete v vs, [e | e <- es, fst e /= v, snd e /= v])
-- find one minimal element
minimal :: Eq a => Digraph a -> a
minimal (vs,es) = head [v | v <- vs, v `minimalIn` es]
minimalIn :: Eq a => a -> Edges a -> Bool
minimalIn _ [] = True
minimalIn v (e:es) | v == snd e = False
| otherwise = minimalIn v es
flatten :: [(a,a)] -> [a]
flatten [] = []
flatten ((x,y):xys) = x : y : flatten xys
sortVia :: Eq a => Rel a -> [a] -> [a]
sortVia rel = sortOn (`elemIndex` total rel)
verify :: Eq a => Rel a -> [a] -> Bool
verify rel xs = not $ any (flip find xs . swap) rel where
find (x,y) = (y `elem`) . dropWhile (/= x)
test :: Ord a => Rel a -> [a] -> Bool
test rel xs = verify rel (sortVia rel xs)
main = do
stdin <- try getLine :: IO (Either IOException String)
case stdin of
Right raw -> do
case readMaybe raw :: Maybe (Rel Char, [Char]) of
Just (rel,xs) -> putStr $ if test rel xs then "." else "X"
_ -> putStr "?"
main
_ -> putStrLn ""