import Data.Array.Unboxed;
import Data.Bits;
import Data.Char;
import Data.List;
import Numeric;

type Perm = [Int]
type Problem = [Perm]
type Comb = [Int]
type Reduction = [Comb]
type Input = (Int,Int,Integer)
type Case = (Problem,Problem,Reduction)

-- 1. list functions

-- all ways to insert an element into a list (n+1 for a list of length n)
insert_everywhere :: a -> [a] -> [[a]]
insert_everywhere e []     = [[e]]
insert_everywhere e (x:xs) = (e:x:xs) : [ x : ys | ys <- insert_everywhere e xs ]

-- is a list a subsequence of another list?
subseq :: Eq a => [a] -> [a] -> Bool
subseq []     ys              = True
subseq (x:xs) []              = False
subseq (x:xs) (y:ys) | x == y = subseq xs ys
subseq (x:xs) (y:ys)          = subseq (x:xs) ys

-- 2. permutations (as list of ints)

-- from n elements [1..n] choose k, taking their order into account (n*(n-1)*...*(n-k+1) ways)
all_combs :: Int -> Int -> [Comb]
all_combs n 0 = [[]]
all_combs n k = concat $ [ all_combs (n-1) k | k < n ] ++ [ insert_everywhere n p | p <- all_combs (n-1) (k-1) ]

-- permutations of n elements [1..n] (n*(n-1)*...*2*1 ways)
all_perms :: Int -> [Perm]
all_perms n = all_combs n n

-- permute the elements of a list (composition of tuples)
compose :: [a] -> Perm -> [a]
compose ys xs = [ (ys !! (x-1)) | x <- xs ]

-- composition table of permutations
comp_table :: UArray (Int,Int) Int
comp_table = array ((0,0),(n-1,n-1)) [ ((i,j),2^k) | (i,p1) <- ps , (j,p2) <- ps , (k,p3) <- ps , p3 == compose p1 p2 ]
  where ps = zip [0..] $ reverse $ sort $ all_perms 4
        n = length ps

-- 3. encoding sets (as bits of ints)

-- elements of xs corresponding to set bits of b
decode :: Integral b => [a] -> b -> [a]
decode xs b = [ x | (x,True) <- zip xs bs ]
  where bs = map odd $ iterate (`div` 2) b

-- compose each permutation in ps with the set of permutations represented as b
compcodes :: Int -> [Int] -> [Int]
compcodes b ps = [ sum [ comp_table ! (p1,p2) | p2 <- bs ] | p1 <- ps ]
  where bs = filter (testBit b) [0..23]

-- 4. problem specific functions

-- read the hexadecimal description of a reduction
parse :: String -> Input
parse s0 = head [ (p1,p2,rr)
  | ('0',s1) <- readLitChar s0
  , ('x',s2) <- readLitChar s1
  , (p1 ,s3) <- readHex s2
  , ('<',s4) <- readLitChar s3
  , ('=',s5) <- readLitChar s4
  , ('0',s6) <- readLitChar s5
  , ('x',s7) <- readLitChar s6
  , (p2 ,s8) <- readHex s7
  , (' ',s9) <- readLitChar s8
  , (rr ,"") <- readHex s9 ]

-- build the reduction from its encoding
construct :: Input -> Case
construct (p1,p2,rr) = (decode ps p1 , decode ps p2 , decode cs rr)
  where ps = reverse $ sort $ all_perms 4
        cs = reverse $ sort $ all_combs 5 4

-- verify co-reducibility
co_red :: Case -> Bool
co_red (p1,p2,rr) = and [ elem t1 p1 == or [ t1 `subseq` t2 && and [ or [ compose r p `subseq` t2 | p <- p2 ] | r <- rr ] | t2 <- all_perms 5 ] | t1 <- all_perms 4 ]

-- calculate the list of reductions among the symmetric problems
symmetric :: Int -> [(Int,Int)]
symmetric k = concat [ rotate $ sort $ nub symm | pc <- [0..2^n-1] , let symm = compcodes pc [0..n-1] , minimum symm == pc ]
  where n = length $ all_perms k
        rotate xs = zip xs (tail xs ++ [head xs])

-- the edges of the reduction graph
all_edges :: [Input] -> [(Int,Int)]
all_edges rs = [ (p1,p2) | (p1,p2,_) <- rs ] ++ symmetric 4 ++ [ (p,n-2) | p <- [0..n-1] ]
  where n = 2 ^ (length (all_perms 4))

-- write the hexadecimal description of an edge of the reduction graph
unparse :: (Int,Int) -> String
unparse (p1,p2) = (showString "0x" . showHex p1 . showString " 0x" . showHex p2) ""

main :: IO ()
main =
  do input <- getContents
     let reductions = map parse $ filter (/="") $ lines input
     case filter (not . co_red . construct) reductions of
       [] -> mapM_ (putStrLn . unparse) $ all_edges reductions