module Main where

import Input


egcd :: Integer -> Integer -> (Integer, Integer, Integer)
egcd m n = go 1 0 m 0 1 n
  where
    go a1 b1 r1 _  _  0  = (r1, a1, b1)
    go a1 b1 r1 a2 b2 r2 =
        let (q, r) = r1 `divMod` r2
        in go a2 b2 r2 (a1 - q * a2) (b1 - q * b2) r

-- multiplicative inverse of k mod n
multinv :: Integer -> Integer -> Integer
multinv k n =
    let (1, x, _) = egcd k n  -- x * k + y * n = 1  =>  x * k = 1 mod n
    in x

-- Affine multiplier addend modulus
data Affine = Affine Integer Integer Integer
  deriving (Show)

instance Semigroup Affine where
    Affine a1 b1 m1 <> Affine a2 b2 m2
        | m1 == m2 = Affine ((a1 * a2) `mod` m1) ((a1 * b2 + b1) `mod` m1) m1
        | otherwise = error "<>'ing incompatible Affine's"

apply :: Affine -> Integer -> Integer
apply (Affine a b m) x = (a * x + b) `mod` m

inverse :: Affine -> Affine
inverse (Affine a b m) = Affine (multinv a m) 0 m <> Affine 1 (-b) m

power :: Semigroup m => m -> Int -> m
power x 1 = x
power x n | n < 1 = error "non-positive exponent in 'power'"
          | even n = power (x <> x) (n `quot` 2)
          | otherwise = power x (n - 1) <> x

parse :: String -> (Integer, Integer)
parse ('c':'u':'t':' ':s) = (1, negate (read s))
parse ('d':_:_:_:_:'w':s) = (read (drop 14 s), 0)
parse ('d':_:_:_:_:'i':_) = (-1, -1)
parse _ = undefined

main :: IO ()
main = do
    techlist <- map parse <$> getInput 22

    let technique1 = foldl1 (<>) [Affine a b 10007 | (a, b) <- reverse techlist]
        technique2 = foldl1 (<>) [Affine a b 119315717514047 | (a, b) <- reverse techlist]

    print (apply technique1 2019)
    print (apply (power (inverse technique2) 101741582076661) 2020)