import List(transpose)
-- import Random nicht mit gransim (gransim ist zu alt :-( )

main :: IO ()
main =  putStr (concat (map find hidden))

find :: [Char] -> String
find w = find' grid w 

-- find:
---------------------------------------------------------------------------
find' :: [[Char]] -> [Char] -> String
find' grid word = word ++ " " ++ (concat dirs) ++ "\n"
  where dirs = map snd (forw ++ back)

        forw = filter (any (contains word) . fst)
               [(r,"right "), (d,"down "), (dl,"downleft "), (ul,"upleft ")]
        back = filter (any (contains drow) . fst)
               [(r,"left "), (d,"up "), (dl,"upright "), (ul,"downright ")]
        drow = reverse word

        r  = grid
        d  = transpose grid
        dl = diagonals grid
        ul = diagonals (reverse grid)

-- diagonals:
-- zipinit:
---------------------------------------------------------------------------
diagonals [r]    = map (:[]) r
diagonals (r:rs) = zipinit r ([]:diagonals rs)

zipinit []     ys     = ys
zipinit (x:xs) (y:ys) = (x : y) : zipinit xs ys

-- contains:
-- prefix:
-- suffixes:
---------------------------------------------------------------------------
contains xs ys = any (prefix xs) (suffixes ys)

suffixes [] = []
suffixes xs = xs : suffixes (tail xs)

prefix []     ys     = True
prefix xs     []     = False
prefix (x:xs) (y:ys) = x == y && prefix xs ys

---------------------------------------------------------------------------
grid = [['Y', 'I', 'O', 'M', 'R', 'E', 'S', 'K', 'S', 'T'],
        ['A', 'E', 'H', 'Y', 'G', 'E', 'H', 'E', 'D', 'W'],
        ['Z', 'F', 'I', 'A', 'C', 'N', 'I', 'T', 'I', 'A'],
        ['N', 'T', 'O', 'C', 'O', 'M', 'V', 'O', 'O', 'R'],
        ['E', 'R', 'D', 'L', 'O', 'C', 'E', 'N', 'S', 'M'],
        ['Z', 'O', 'U', 'R', 'P', 'S', 'R', 'N', 'D', 'A'],
        ['O', 'Y', 'A', 'S', 'M', 'O', 'Y', 'E', 'D', 'L'],
        ['R', 'N', 'D', 'E', 'N', 'L', 'O', 'A', 'I', 'T'],
        ['F', 'I', 'W', 'I', 'N', 'T', 'E', 'R', 'R', 'C'],
        ['F', 'E', 'Z', 'E', 'E', 'R', 'F', 'T', 'F', 'I'],
        ['I', 'I', 'D', 'T', 'P', 'H', 'U', 'B', 'R', 'L'],
        ['C', 'N', 'O', 'H', 'S', 'G', 'E', 'I', 'O', 'N'],
        ['E', 'G', 'M', 'O', 'P', 'S', 'T', 'A', 'S', 'O'],
        ['T', 'G', 'F', 'F', 'C', 'I', 'S', 'H', 'T', 'H'],
        ['O', 'T', 'B', 'C', 'S', 'S', 'N', 'O', 'W', 'I']]

hidden = ["COSY", "SOFT", "WINTER", "SHIVER", "FROZEN", "SNOW",
          "WARM", "HEAT", "COLD", "FREEZE", "FROST", "ICE" ]


alphabet = ['A'..'Z']
mkGrid :: Int -> Int -> [[Char]]
mkGrid n seed = let range  = (0,length alphabet - 1)
		    char n = alphabet!!n
		    g      = mkStdGen seed
		    chars  = map char (take (n*n) (randomRs range g))
                in (splitIntoN n chars)
splitIntoN :: Int -> [a] -> [[a]]
splitIntoN n [] = []
splitIntoN n xs = kopf : splitIntoN n rest
    where (kopf,rest) = splitAt n xs

-- ab hier nur fuer gransim... ersetzt das Random-Modul

type StdGen = Int -- simply a seed...
mkStdGen = id


randomRs :: (Int,Int) -> StdGen -> [Int]
randomRs (lo,hi) seed = map adjust (random2Ints (1+seed) (seed*seed))
    where adjust n | lo < hi = lo + (n `mod` (hi - lo))
		   | otherwise = error "lo >= hi"

-- random-number generator stolen from the `hbc'-library.
random2Ints :: Int -> Int -> [Int]
random2Ints s1 s2
   | s1 < 1 || s1 > 2147483562  =  error "random2Ints: Bad first seed."
   | s2 < 1 || s2 > 2147483398  =  error "random2Ints: Bad second seed."
   | otherwise                  =  rands s1 s2

rands :: Int -> Int -> [Int]
rands s1 s2
     | z < 1                    =  z + 2147483562 : rands s1'' s2''
     | otherwise                =  z              : rands s1'' s2''
     where k                    =  s1 `div` 53668
           s1'                  =  40014 * (s1 - k * 53668) - k * 12211
           s1'' | s1' < 0       =  s1' + 2147483563
                | otherwise     =  s1'
           k'                   =  s2 `div` 52774
           s2'                  =  40692 * (s2 - k' * 52774) - k' * 3791
           s2'' | s2' < 0       =  s2' + 2147483399
                | otherwise    =  s2'
           z                    =  s1'' - s2''