module Main where

import Data.Bits

parse :: String -> Int
parse x =
    case words x of
        ["Generator", _, "starts", "with", y] -> read y
        _ -> 0

type Generator = Int -> Int

generator :: Int -> Generator
generator factor previous = (previous * factor) `rem` 2147483647
{-# INLINE generator #-}

generatorA, generatorB :: Generator
generatorA = generator 16807
generatorB = generator 48271

matchLo :: (Num a, Bits a) => a -> a -> Bool
matchLo l r = l .&. 0xffff == r .&. 0xffff
{-# INLINE matchLo #-}

day15 :: Int -> [Int] -> [Int] -> Int
day15 limit as bs = length . filter (uncurry matchLo) . take limit $ zip as bs
{-# INLINE day15 #-}

part1, part2 :: Int -> Int -> Int -> Int
part1 limit a b = day15 limit (iterate generatorA a) (iterate generatorB b)
part2 limit a b =
    day15
        limit
        (filter (4 `divides`) $ iterate generatorA a)
        (filter (8 `divides`) $ iterate generatorB b)
  where
    a `divides` b = b `rem` a == 0

main :: IO ()
main = do
    a <- parse <$> getLine
    b <- parse <$> getLine
    print $ part1 40000000 a b
    print $ part2 5000000 a b