-- ACM Pacific NW Region Programming Contest, 11 November 2000
-- Problem B, Base Addition
-- Sergio Antoy, Thu Jun  7 11:23:34 PST 2001

str2int s = map hex2int s
hex2int x | ord '0' <= ord x && ord x <= ord '9' = ord x - ord '0'
          | ord 'A' <= ord x && ord x <= ord 'Z' = ord x - ord 'A' + 10

addWithBase base op1 op2 = carry 0 (aux op1 op2)
   where aux [] [] = []
         aux [] (x:xs) = x:xs
         aux (x:xs) [] = x:xs
         aux (x:xs) (y:ys) = x+y : aux xs ys
         carry 0 [] = []
         carry 1 [] = [1]
         carry c (x:xs) = if z >= base then z-base : carry 1 xs
                                       else      z : carry 0 xs
            where z = x + c

solve str1 str2 str3 = format test
   where setup x = reverse (str2int x)
         format [] = str1 ++ " + " ++ str2 ++ " != " ++ str3
         format (base:_) = str1 ++ " + " ++ str2 ++ " = " ++ str3 ++ 
                           " in base " ++ (show base)
         test = [x | x <- [2..36],
                     addWithBase x (setup str1) (setup str2) == (setup str3)]

doOne ["0"] = return ()
doOne (str1:str2:str3:rest) = putStrLn (solve str1 str2 str3) >> doOne rest

main = do input <- readFile "b.dat"
          doOne (lines input)