```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

parse :: String -> Input
parse s0 = head [ (p1,p2,rr)
, (p1 ,s3) <- readHex s2
, (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

```