module Main where
import qualified Data.Sequence as Sq
import Data.Maybe
import Data.Sequence (Seq,(<|), (><), (|>),ViewL(..), viewl)
import System.IO

type Base = Char
type DNA = Seq Base
type RNA = Seq [Base]
data PatternNode = BaseP Base | SkipP Int | SearchP [Base] | LP | RP
		deriving (Show, Read)
type Pattern = Seq PatternNode

type Environment = Seq DNA

data TemplateNode = BaseT Base | ProtectT Int Int | AsNatT Int
		deriving (Show, Read)
type Template = Seq TemplateNode

consumePattern :: DNA -> ((Maybe (DNA, Pattern)), RNA)
consumePattern dna00 = cp 0 dna00 Sq.empty Sq.empty where
 cp :: Int -> DNA -> Pattern -> RNA -> ((Maybe (DNA, Pattern)), RNA)
 cp level dna0 pat rna
  = level `seq` dna0 `seq` pat `seq` rna `seq`
    case viewl dna0 of
	EmptyL -> (Nothing, rna)
	('C' :< dna9) -> cp level dna9 (pat |> BaseP 'I') rna
	('F' :< dna9) -> cp level dna9 (pat |> BaseP 'C') rna
	('P' :< dna9) -> cp level dna9 (pat |> BaseP 'F') rna
	('I' :< dna1) ->
	  case viewl dna1 of
	    EmptyL -> (Nothing, rna)
	    ('C' :< dna9) -> cp level dna9 (pat |> BaseP 'P') rna
	    ('P' :< dna2) -> case consumeNat dna2 of
				Just (n, dna9) ->
					cp level dna9 (pat |> SkipP n) rna
				Nothing -> (Nothing, rna)
	    ('F' :< dna2) -> let dna3 = Sq.drop 1 dna2
				 (bases, dna9) = consumeConst dna3 in
					cp level dna9 (pat |> SearchP bases) rna
	    ('I' :< dna2) ->
	      case viewl dna2 of
		EmptyL -> (Nothing, rna)
		('P' :< dna9) -> cp (level+1) dna9 (pat |> LP) rna
		('I' :< dna3) -> let
					(r, dna9) = Sq.splitAt 7 dna3
					rna_tip = sequence2list r
					in cp level dna9 pat (rna|>rna_tip)
		(_ :< dna9) | level==0 -> (Just (dna9,pat), rna)
			    | otherwise-> cp (level-1) dna9 (pat |> RP) rna

-- TODO: make it Maybe because it can fail
consumeNat :: DNA -> Maybe (Int, DNA)
consumeNat dna0 = cn 0 1 dna0 where
	cn :: Int -> Int -> DNA -> Maybe (Int, DNA)
	cn n p0 dna = let p1 = p0*2 in
		case viewl dna of
			('P' :< dna9) -> Just $ (n, dna9)
			('C' :< dna9) -> cn (n+p0) p1 dna9
			('I' :< dna9) -> cn n p1 dna9
			('F' :< dna9) -> cn n p1 dna9
			EmptyL -> Nothing

consumeConst :: DNA -> ([Base], DNA)
consumeConst dna00 = cc [] dna00 where
	cc :: [Base] -> DNA -> ([Base], DNA)
	cc base dna0 = case viewl dna0 of
		EmptyL -> (reverse base, dna0)
		('C' :< dna9) -> cc ('I':base) dna9
		('F' :< dna9) -> cc ('C':base) dna9
		('P' :< dna9) -> cc ('F':base) dna9
		('I' :< dna1) -> case viewl dna1 of
			('C' :< dna9) -> cc ('P':base) dna9
			_ -> (reverse base,dna0)

sequence2list :: Seq a -> [a]
sequence2list s = case viewl s of
			EmptyL -> []
			(a :< rest) -> a:sequence2list rest

consumeTemplate :: DNA -> ((Maybe (DNA, Template)), RNA)
consumeTemplate dna00 = ct dna00 Sq.empty Sq.empty where
 ct :: DNA -> Template -> RNA -> ((Maybe (DNA, Template)), RNA)
 ct dna0 tpl rna
  = dna0 `seq` tpl `seq` rna `seq`
    case viewl dna0 of
	EmptyL -> (Nothing, rna)
	('C' :< dna9) -> ct dna9 (tpl |> BaseT 'I') rna
	('F' :< dna9) -> ct dna9 (tpl |> BaseT 'C') rna
	('P' :< dna9) -> ct dna9 (tpl |> BaseT 'F') rna
	('I' :< dna1) ->
	  case viewl dna1 of
	    EmptyL -> (Nothing, rna)
	    ('C' :< dna9) -> ct dna9 (tpl |> BaseT 'P') rna
	    ('I' :< dna2) -> case viewl dna2 of
		('I' :< dna3) -> let
				  (r, dna9) = Sq.splitAt 7 dna3
				  rna_tip = sequence2list r
				  in ct dna9 tpl (rna|>rna_tip)
		('P' :< dna3) -> case consumeNat dna3 of
					Nothing -> (Nothing, rna)
					Just (n, dna9) ->
						ct dna9 (tpl |> AsNatT n) rna
		(c :< dna9) -> (Just (dna9, tpl), rna)
	    (c :< dna2) -> case consumeNat dna2 of
			    Nothing -> (Nothing, rna)
			    Just (el, dna3) ->
				case consumeNat dna3 of
				  Nothing -> (Nothing, rna)
				  Just (n, dna9) ->
					ct dna9 (tpl |> ProtectT el n) rna

matchReplace :: DNA -> Pattern -> Template -> DNA
matchReplace dna0 pat tpl =
	let res = matcher dna0 pat in
	case res of
		Nothing -> dna0
		Just (env,dna1) -> replacer dna1 env tpl

-- if failed then returns nothing
matcher :: DNA -> Pattern -> Maybe (Environment, DNA)
matcher dna pat0 = mt pat0 0 [] Sq.empty where
 mt :: Pattern -> Int -> [Int] -> Environment -> Maybe (Environment, DNA)
 mt pat0 pos stack env = case viewl pat0 of
	EmptyL -> Just (env, Sq.drop pos dna)
	(BaseP c :< pat9) -> if Sq.index dna pos == c
				then mt pat9 (pos + 1) stack env
				else Nothing
	(SkipP n :< pat9) -> if n+pos > Sq.length dna then Nothing
				else mt pat9 (pos + n) stack env
	(SearchP str :< pat9) -> case searchSequence dna str pos of
					Nothing -> Nothing
					Just n -> mt pat9 n stack env
	(LP :< pat9) -> mt pat9 pos (pos:stack) env
	(RP :< pat9) -> let	(shead:stail) = stack
				nenv = Sq.take (pos - shead) $
					Sq.drop shead $ dna
			in mt pat9 pos stail (env |> nenv)

searchSequence :: DNA -> [Base] -> Int -> Maybe Int
searchSequence dna0 str pos0 = sS (Sq.drop pos0 dna0) pos0 where
  len = length str
  sS :: DNA -> Int -> Maybe Int
  sS dna offset	| Sq.length dna < len = Nothing
		| eq (Sq.take len dna) str = Just (offset + len)
		| otherwise = sS (Sq.drop 1 dna) (offset+1)
  eq :: DNA -> [Base] -> Bool
  eq d [] = Sq.null d
  eq d (x:xs) = case viewl d of
			EmptyL -> False
			(f:<rest) -> if x /= f then False else eq rest xs

replacer :: DNA -> Environment -> Template -> DNA
replacer dna0 env tpl = rp Sq.empty tpl >< dna0 where
  rp :: DNA -> Template -> DNA
  rp prefix tpl0 = case viewl tpl0 of
	EmptyL -> prefix
	(BaseT b:< tpl9) -> rp (prefix |> b) tpl9
	(ProtectT el n :< tpl9) -> rp (prefix ><
					protector el (Sq.index env n)) tpl9
	(AsNatT n :< tpl9) -> rp (prefix ><
				asNatDNA (Sq.length $ Sq.index env n)) tpl9

protector :: Int -> DNA -> DNA
protector 0 d = d
protector n d = protector (n-1) $ quoteDNA d

quoteDNA :: DNA -> DNA
quoteDNA d = quoteDNA' d Sq.empty where
  quoteDNA' :: DNA -> DNA -> DNA
  quoteDNA' dfrom dto = case viewl dfrom of
		EmptyL -> dto
		('I' :< rest) -> quoteDNA' rest (dto |> 'C')
		('C' :< rest) -> quoteDNA' rest (dto |> 'F')
		('F' :< rest) -> quoteDNA' rest (dto |> 'P')
		('P' :< rest) -> quoteDNA' rest (dto |> 'I' |> 'C')

asNatDNA :: Int -> DNA
asNatDNA n = asnat n Sq.empty where
 asnat :: Int -> DNA -> DNA
 asnat 0 prefix = prefix |> 'P'
 asnat n prefix = let (q,r) = divMod n 2 in case r of
			0 -> asnat q (prefix |> 'I')
			1 -> asnat q (prefix |> 'C')

outputRNA :: RNA -> IO ()
outputRNA rna = case Sq.viewl rna of
			EmptyL -> return ()
			(:<) h rest -> putStrLn h >> outputRNA rest

pDebugString :: Bool
pDebugString = False

debugStr :: String -> IO ()
debugStr str = if pDebugString then hPutStr stdout str else return ()
debugPrint :: Show a => a -> IO ()
debugPrint a = if pDebugString then hPrint stdout a else return ()
debugPrintTag :: Show a => String -> a -> IO ()
debugPrintTag s a = debugStr s >> debugPrint a

cerrDNA :: DNA -> IO ()
cerrDNA dna | pDebugString = do
				putStr $ show $ Sq.length dna
				putStr ": "
				putStrLn $ sequence2list $ Sq.take 100 $ dna
	    | otherwise = return ()

cerrPattern :: Pattern -> IO ()
cerrPattern pat = debugPrintTag "pattern = " pat

cerrTemplate :: Template -> IO ()
cerrTemplate tpl = do debugPrintTag "template = " tpl

-- executeOnce :: DNA -> ((Maybe DNA), RNA)

executeOnceIO :: DNA -> IO (Maybe DNA)
executeOnceIO dna0 = do
	cerrDNA dna0
	let (postpattern, rna0) = consumePattern $! dna0
	outputRNA rna0
	case postpattern of
		Nothing -> return Nothing
		Just (dnap, pattern) -> do
			cerrPattern pattern
			let (posttemplate, rna1) = consumeTemplate $! dnap
			outputRNA rna1
			case posttemplate of
				Nothing -> return Nothing
				Just (dnat, template) -> do
					cerrTemplate template
					let result = matchReplace dnat pattern template
					return $ Just result

executeIO :: DNA -> IO ()
executeIO dna0 = executioner dna0 0 where
	executioner :: DNA -> Int -> IO ()
	executioner dna turns = do
		debugPrintTag "Count :: " turns
		res <- executeOnceIO $! dna
		case res of
			Nothing -> return ()
			Just dna' -> if (Sq.null dna') then return ()
					else executioner dna' (turns+1)

testDNA :: [DNA]
testDNA = map Sq.fromList ["IIPIPICPIICICIIFICCIFPPIICCFPC",
			"IIPIPICPIICICIIFICCIFCCCPPIICCFPC",
			"IIPIPIICPIICIICCIICFCFC"]

main :: IO ()
main = do
	input <- getLine
	executeIO $ Sq.fromList input