-- Author: Yuchen Pei (me@ypei.me)
{-# LANGUAGE BangPatterns #-}

import Data.Int

stepA :: Int -> Int
stepA !x = x * 16807 `rem` 2147483647
stepB :: Int -> Int
stepB !x = x * 48271 `rem` 2147483647

stepA' :: Int -> Int
stepA' !x = until ((==0) . flip rem 4) stepA (stepA x)

stepB' :: Int -> Int
stepB' !x = until ((==0) . flip rem 8) stepB (stepB x)

toInt16 :: Int -> Int16
toInt16 = fromIntegral

stepAB :: ((Int, Int), Int) -> ((Int, Int), Int)
stepAB ((!x, !y), !n) = ((stepA x, stepB y), if (toInt16 x) == (toInt16 y) then n + 1 else n)

stepAB' :: ((Int, Int), Int) -> ((Int, Int), Int)
stepAB' ((!x, !y), !n) = ((stepA' x, stepB' y), if (toInt16 x) == (toInt16 y) then n + 1 else n)

f :: Int -> ((Int, Int), Int) -> ((Int, Int), Int)
f 0 acc = acc
f m !acc = f (m - 1) (stepAB acc)

f' :: Int -> ((Int, Int), Int) -> ((Int, Int), Int)
f' 0 acc = acc
f' m !acc = f' (m - 1) (stepAB' acc)

solve1 :: (Int, Int) -> Int
solve1 (x, y) = snd $ f 40000000 ((x, y), 0)

solve2 :: (Int, Int) -> Int
solve2 (x, y) = snd $ f' 5000000 ((x, y), 0)

input :: (Int, Int)
input = (783, 325)

input0 = (65, 8921) :: (Int, Int)

--main = (putStrLn . show . solve1) input
main = (putStrLn . show . solve2) input