extgcd :: Integer -> Integer -> (Integer, Integer) extgcd a 0 = (1, 0) extgcd a b = (y, x - (a `div` b) * y) where (x, y) = extgcd b (a `mod` b) min_k :: Integer -> Integer -> Integer min_k a c | c < 0 = (-c + a - 1) `div` a | otherwise = -(c `div` a) collision_check :: [Integer] -> Bool collision_check [w, h, d, hx, hy, vx, vy, xs, ys] | c `mod` g /= 0 = False | otherwise = (x - hx) ^ 2 + (y - hy) ^ 2 <= (vx ^ 2 + vy ^ 2) * d ^ 2 where a = 2 * w * vy b = 2 * h * vx c = vx * (ys - hy) - vy * (xs - hx) g = gcd a b a' = a `div` g b' = b `div` g c' = c `div` g (alpha, beta) = extgcd a' b' min_n = min_k (2 * w) (xs - hx - 1) min_m = min_k (2 * h) (ys - hy - 1) k = max (min_k b' (c' * alpha - min_n)) (min_k a' (-c' * beta - min_m)) n = b' * k + c' * alpha m = a' * k - c' * beta x = 2 * w * n + xs y = 2 * h * m + ys line_check :: [Integer] -> Bool line_check [w, d, mx, hx, vx] = dist <= vx * d where dist = if (mx > hx) then mx - hx else (w - hx) * 2 + hx - mx check :: [Integer] -> Bool check [w, h, d, mx, my, hx, hy, vx, vy] | vx < 0 = check [w, h, d, w - mx, my, w - hx, hy, -vx, vy] | vy < 0 = check [w, h, d, mx, h - my, hx, h - hy, vx, -vy] | vx == 0 = (mx == hx) && line_check [h, d, my, hy, vy] | vy == 0 = (my == hy) && line_check [w, d, mx, hx, vx] | otherwise = any (\(xs, ys) -> collision_check [w, h, d, hx, hy, vx, vy, xs, ys]) [ (mx, my), (mx + (w - mx) * 2, my), (mx, my + (h - my) * 2), (mx + (w - mx) * 2, my + (h - my) * 2) ] readInt :: IO Int readInt = fmap read getLine readInts :: IO [Integer] readInts = fmap ((map read) . words) getLine printer :: Bool -> IO () printer True = putStrLn "Hit" printer _ = putStrLn "Miss" main = do q <- readInt inputs <- sequence (replicate q readInts) mapM_ (printer . check) inputs