import List
import Array

data Remoteness = R Int | RMin deriving (Show, Eq)
unR (R a) = a
data Suspense = S Int | SMin deriving (Show, Eq)
unS (S a) = a

type RList = [Remoteness]
type SList = [Suspense]

instance Ord Remoteness where
    RMin < _ = True
    _ < RMin = False
    (R a) < (R b) = (-1)^a * (b+1) > (-1)^b * (a+1)
    a <= b = a < b || a == b

instance Ord Suspense where
    SMin < _ = True
    _ < SMin = False
    (S a) < (S b) = (-1)^a * a > (-1)^b * b
    a <= b = a < b || a == b

maxl :: Ord a => [a] -> [a] -> [a]
maxl = zipWith max

scs :: RList -> RList -> RList
scs rl1 rl2 = zipWith (\ (R a) (R b) -> R (min a b)) rl1 rl2
lcs :: SList -> SList -> SList
lcs sl1 sl2 = zipWith (\ (S a) (S b) -> S (max a b)) sl1 sl2

rstop :: RList -> RList
-- rstop rl = (head rl) : rstop' (head rl) (tail rl) 1
--     where rstop' (R rp) (R r : rs) i =
-- 	      (R r) :
-- 		    if rp == i-1 && r == i
-- 		    then map R [i+1..]
-- 		    else rstop' (R r) rs (i+1)
rstop = id

rchop :: RList -> RList
rchop rl = (head rl) : rchop' (head rl) (tail rl) 1
    where rchop' (R rp) (R r : rs) i =
	      (R r) :
		    if rp == i-1 && r == i
		    then []
		    else rchop' (R r) rs (i+1)

sstop :: SList -> SList
-- sstop sl = (head sl) : sstop' (head sl) (tail sl) 1
--     where sstop' (S sp) (S s : ss) i =
-- 	      (S s) :
--  		    if sp == s
--  		    then repeat (S s)
--  		    else sstop' (S s) ss (i+1)
sstop = id

schop :: SList -> SList
schop sl = (head sl) : schop' (head sl) (tail sl) 1
    where schop' (S sp) (S s : ss) i =
	      (S s) :
 		    if sp == s
 		    then []
 		    else schop' (S s) ss (i+1)

rgame :: Int -> RList
rgame n = [ R (max i n) | i <- [0..] ]

sgame :: Int -> SList
sgame n = [ S (min i n) | i <- [0..] ]

game :: Int -> (RList, SList)
game n = (rgame n, sgame n)

rtosat :: RList -> Int -> Suspense
rtosat rl n = S (-1 + length (fst (span (\ x -> x `mod` 2 == head p) p)))
    where p = map (`mod` 2) $ zipWith (\ (R a) (R b) -> min a b) rl (rgame n)

rtos :: RList -> SList
rtos (RMin : _) = repeat SMin
rtos rl = sstop $ [ rtosat rl n | n <- [0..] ]

storat :: SList -> Int -> Remoteness
storat sl n = R (-1 + length (fst (span (\x -> x `mod` 2 == head p) p)))
    where p = map (`mod` 2) $ zipWith3 (\ (S a) (S b) i -> i + max a b)
	      sl (sgame n) [0..]

stor :: SList -> RList
stor (SMin : _) = repeat RMin
stor sl = rstop $ [ storat sl n | n <- [0..] ]

rinc :: RList -> RList
rinc rl = map (\ (R a) -> (R (a+1))) $ (head rl) : rl

sinc :: SList -> SList
sinc sl = S 0 : map (\ (S a) -> (S (a+1))) sl

opts :: [RList] -> [SList] -> (RList, SList)
opts rls sls = (rl', rtos rl')
    where rl' = rstop $ (foldl1 maxl ((repeat RMin) : map rinc rls))
		`maxl` stor (foldl1 maxl ((repeat SMin) : map sinc sls))

r :: Int
r = 100
c :: Int
c = 100

sequences :: Array (Int,Int) (RList, SList)
sequences = array ((0,1),(r,c)) $
	    [ ((0,j), game 0) | j <- [1..c] ] ++
	    [ ((i,j), opts
	       [ scs (fst $ sequences ! (i,k)) (fst $ sequences ! (i,j-k))
		 | k <- [1..j-1], k <= j-k ]
	       [ lcs (snd $ sequences ! (k,j)) (snd $ sequences ! (i-k-1,j))
		 | k <- [0..i-1], k <= i-k-1 ]
	      ) | i <- [1..r], j <- [1..c] ]

main :: IO ()
main = foldl1 (>>) $
       [
	do
	putStr (show i)
	putStr " "
	putStr (show j)
	putStr " "
	print $ (\ (a,b) -> (rchop a, schop b)) $ sequences ! (i,j)
	| i <- [0..r], j <- [1..c] ]