{-
http://www.acm-japan.org/past-icpc/domestic2006/contest/all_ja.html#section_E
2007.06.15
nisikawa
-}
import Text.ParserCombinators.Parsec
data Genom = S String | G Integer [Genom] deriving Show
exec :: String -> Integer -> Char
exec line idx = exec' idx $ run line
where exec' idx [] = '0'
exec' idx (x:xs) = let l = dataLength x in if l > idx then at idx l x else exec' (idx - l) xs
dataLength (S s) = toInteger $ length s
dataLength (G n gs) = n * (sum $ map dataLength gs)
at idx len (S s) = let i = idx `mod` len in s !! (fromInteger i)
at idx len (G n gs) = exec' idx $ concat $ replicate (fromInteger n) gs
run line = case (parse genoms "" line) of
Left e -> error $ show e
Right gs -> gs
genoms = do
g <- genom
gs <- try genoms <|> return []
return $ g:gs
genom = try parseS <|> parseG
parseS = do
s <- many1 $ oneOf "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
return $ S s
parseG = do
i <- many1 digit
gs <- try (parseS >>= \s -> return [s]) <|> paren
return $ G (read i) gs
paren = do
char '('
gs <- genoms
char ')'
return gs
