import Control.Monad
import Data.List hiding (insert)
import Data.Maybe


data State = State Int [Int]

initState :: State
initState = State 1 [0]

step :: Int -> State -> State
step stepsize (State cur arr) = State cur (take (length arr) $ drop stepsize $ cycle arr)

insert :: State -> State
insert (State cur (hd:tl)) = State (cur+1) (cur : tl ++ [hd])

data State2 = State2 {s2Len :: Int, s2Cur :: Int, s2Value :: Int}

initState2 :: State2
initState2 = State2 1 0 0

step2 :: Int -> State2 -> State2
step2 stepsize (State2 len cur val) = State2 len ((cur + stepsize) `mod` len) val

insert2 :: State2 -> State2
insert2 (State2 len 0 val) = State2 (len+1) 1 len
insert2 (State2 len cur val) = State2 (len+1) (cur+1) val

main :: IO ()
main = do
    stepsize <- liftM read (readFile "17.in")

    let State _ end = iterate (insert . step stepsize) initState !! 2017
    print $ end !! 1

    let end2 = iterate (insert2 . step2 stepsize) initState2 !! 50000000
    print $ s2Value end2