{-# LANGUAGE BangPatterns #-} {-# LANGUAGE CPP #-} {-# LANGUAGE DerivingStrategies #-} {-# LANGUAGE FlexibleContexts #-} {-# LANGUAGE GeneralizedNewtypeDeriving #-} {-# LANGUAGE MagicHash #-} {-# LANGUAGE MultiParamTypeClasses #-} {-# LANGUAGE RankNTypes #-} {-# LANGUAGE RecordWildCards #-} {-# LANGUAGE ScopedTypeVariables #-} {-# LANGUAGE TypeApplications #-} {-# LANGUAGE TypeFamilies #-} {-# LANGUAGE UnboxedTuples #-} import Control.Monad import Control.Monad.State import Data.Bits import Data.Bool import Data.Char import Data.Coerce import Data.Functor.Identity import Data.Ratio import Data.Word import GHC.Exts import Unsafe.Coerce import qualified Data.ByteString as BS import qualified Data.ByteString.Char8 as BSC8 import qualified GHC.Integer.GMP.Internals as GMP import qualified Data.Vector.Fusion.Stream.Monadic as VFSM import qualified Data.Vector.Generic as VG import qualified Data.Vector.Generic.Mutable as VGM import qualified Data.Vector.Unboxed as VU import qualified Data.Vector.Unboxed.Mutable as VUM ------------------------------------------------------------------------------- #define MOD 1000000007 #define Fact_CACHE_SIZE 100100 #define LOG_FACT_CACHE_SIZE 100100 ------------------------------------------------------------------------------- fi :: Int -> Integer fi = fromIntegral {-# INLINE fi #-} fI :: Integer -> Int fI = fromInteger {-# INLINE fI #-} floorSqrt :: Int -> Int floorSqrt = floor . sqrt . fromIntegral {-# INLINE floorSqrt #-} floorLog2 :: Int -> Int floorLog2 x = fromIntegral $ unsafeShiftR y 52 - 1023 where y :: Word64 y = unsafeCoerce (fromIntegral x :: Double) {-# INLINE floorLog2 #-} powModInt :: Int -> Int -> Int -> Int powModInt a b c = fI $ GMP.powModInteger (fi a) (fi b) (fi c) {-# INLINE powModInt #-} recipModInt :: Int -> Int -> Int recipModInt a m = fI $ GMP.recipModInteger (fi a) (fi m) {-# INLINE recipModInt #-} gcdext :: Int -> Int -> (Int, Int, Int) -- a * x + b * y = d => (x, y, d) (d = gcd a b) gcdext a b = (x, y, d) where d = gcd a b (x, y) = case GMP.gcdExtInteger (fi a) (fi b) of (# p, q #) -> (fI p, fI q) {-# INLINE gcdext #-} modInv :: Int -> Int -> Int modInv a mo | 1 == g = mkPos i | otherwise = -1 where (i, _, g) = gcdext a mo mkPos x | x < 0 = x + mo | otherwise = x {-# INLINE modInv #-} stream :: Monad m => Int -> Int -> VFSM.Stream m Int stream !l !r = VFSM.Stream step l where step x | x < r = return $ VFSM.Yield x (x + 1) | otherwise = return $ VFSM.Done {-# INLINE [0] step #-} {-# INLINE [1] stream #-} rep :: Monad m => Int -> (Int -> m ()) -> m () rep n = flip VFSM.mapM_ (stream 0 n) {-# INLINE rep #-} streamR :: (Monad m) => Int -> Int -> VFSM.Stream m Int streamR !l !r = VFSM.Stream step (r - 1) where step x | x >= l = return $ VFSM.Yield x (x - 1) | otherwise = return VFSM.Done {-# INLINE [0] step #-} {-# INLINE [1] streamR #-} rev :: (Monad m) => Int -> (Int -> m ()) -> m () rev !n = flip VFSM.mapM_ (streamR 0 n) {-# INLINE rev #-} streamStep :: (Monad m) => Int -> Int -> Int -> VFSM.Stream m Int streamStep !l !r !d = VFSM.Stream step l where step x | x < r = return $ VFSM.Yield x (x + d) | otherwise = return VFSM.Done {-# INLINE [0] step #-} {-# INLINE [1] streamStep #-} infixl 8 `shiftRL`, `unsafeShiftRL` shiftRL :: Int -> Int -> Int shiftRL = unsafeShiftRL {-# INLINE shiftRL #-} unsafeShiftRL :: Int -> Int -> Int unsafeShiftRL (I# x#) (I# i#) = I# (uncheckedIShiftRL# x# i#) {-# INLINE unsafeShiftRL #-} lowerBoundM :: (Monad m) => Int -> Int -> (Int -> m Bool) -> m Int lowerBoundM low high p = go low high where go !low !high | high <= low = return high | otherwise = p mid >>= bool (go (mid + 1) high) (go low mid) where mid = low + unsafeShiftRL (high - low) 1 {-# INLINE lowerBoundM #-} upperBoundM :: (Monad m) => Int -> Int -> (Int -> m Bool) -> m Int upperBoundM low high p = do flg <- p high if flg then return high else subtract 1 <$!> lowerBoundM low high (fmap not.p) {-# INLINE upperBoundM #-} lowerBound :: Int -> Int -> (Int -> Bool) -> Int lowerBound low high p = runIdentity (lowerBoundM low high (return . p)) {-# INLINE lowerBound #-} upperBound :: Int -> Int -> (Int -> Bool) -> Int upperBound low high p = runIdentity (upperBoundM low high (return . p)) {-# INLINE upperBound #-} (.>>.) :: Bits i => i -> Int -> i (.>>.) = unsafeShiftR {-# INLINE (.>>.) #-} (.<<.) :: Bits i => i -> Int -> i (.<<.) = unsafeShiftL {-# INLINE (.<<.) #-} (.>>>.) :: Int -> Int -> Int (.>>>.) = unsafeShiftRL {-# INLINE (.>>>.) #-} ------------------------------------------------------------------------------- -- Input ------------------------------------------------------------------------------- type CParser a = StateT BSC8.ByteString Maybe a runCParser :: CParser a -> BSC8.ByteString -> Maybe (a, BSC8.ByteString) runCParser = runStateT {-# INLINE runCParser #-} int :: CParser Int int = coerce $ BSC8.readInt . BSC8.dropWhile isSpace {-# INLINE int #-} int1 :: CParser Int int1 = fmap (subtract 1) int {-# INLINE int1 #-} char :: CParser Char char = coerce BSC8.uncons {-# INLINE char #-} byte :: CParser Word8 byte = coerce BS.uncons {-# INLINE byte #-} skipSpaces :: CParser () skipSpaces = modify' (BSC8.dropWhile isSpace) {-# INLINE skipSpaces #-} seqInput :: Int -> IO (VU.Vector Int) seqInput n = VU.unfoldrN n (runCParser int) <$> BSC8.getLine {-# INLINE seqInput #-} parseN2 :: Int -> IO (VU.Vector (Int, Int)) parseN2 n = VU.unfoldrN n (runCParser $ (,) <$> int <*> int) <$> BSC8.getContents {-# INLINE parseN2 #-} parseN3 :: Int -> IO (VU.Vector (Int, Int, Int)) parseN3 n = VU.unfoldrN n (runCParser $ (,,) <$> int <*> int <*> int) <$> BSC8.getContents {-# INLINE parseN3 #-} parseN4 :: Int -> IO (VU.Vector (Int, Int, Int, Int)) parseN4 n = VU.unfoldrN n (runCParser $ (,,,) <$> int <*> int <*> int <*> int) <$> BSC8.getContents {-# INLINE parseN4 #-} parseN5 :: Int -> IO (VU.Vector (Int, Int, Int, Int, Int)) parseN5 n = VU.unfoldrN n (runCParser $ (,,,,) <$> int <*> int <*> int <*> int <*> int) <$> BSC8.getContents {-# INLINE parseN5 #-} parseANBN :: Int -> IO (VU.Vector Int, VU.Vector Int) parseANBN n = VU.unzip . VU.unfoldrN n (runCParser $ (,) <$> int <*> int) <$> BSC8.getContents {-# INLINE parseANBN #-} parseANBNCN :: Int -> IO (VU.Vector Int, VU.Vector Int, VU.Vector Int) parseANBNCN n = VU.unzip3 . VU.unfoldrN n (runCParser $ (,,) <$> int <*> int <*> int) <$> BSC8.getContents {-# INLINE parseANBNCN #-} type Query5 = (Int, Int, Int, Int, Int) query5Parser :: CParser Query5 query5Parser = do skipSpaces t <- char case t of '0' -> (,,,,) 0 <$> int <*> int <*> int <*> int _ -> (,,,,) 1 <$> int <*> int <*> pure 0 <*> pure 0 parseQ5 :: Int -> IO (VU.Vector Query5) parseQ5 n = VU.unfoldrN n (runCParser query5Parser) <$> BSC8.getContents {-# INLINE parseQ5 #-} ------------------------------------------------------------------------------- modulus :: Num a => a modulus = MOD {-# INLINE modulus #-} infixr 8 ^% infixl 7 *%, /% infixl 6 +%, -% (+%) :: Int -> Int -> Int (+%) (I# x#) (I# y#) = case x# +# y# of r# -> I# (r# -# ((r# >=# MOD#) *# MOD#)) {-# INLINE (+%) #-} (-%) :: Int -> Int -> Int (-%) (I# x#) (I# y#) = case x# -# y# of r# -> I# (r# +# ((r# <# 0#) *# MOD#)) {-# INLINE (-%) #-} (*%) :: Int -> Int -> Int (*%) (I# x#) (I# y#) = case timesWord# (int2Word# x#) (int2Word# y#) of z# -> case timesWord2# z# im# of (# q#, _ #) -> case minusWord# z# (timesWord# q# m#) of v# | isTrue# (geWord# v# m#) -> I# (word2Int# (plusWord# v# m#)) | otherwise -> I# (word2Int# v#) where m# = int2Word# MOD# im# = plusWord# (quotWord# 0xffffffffffffffff## m#) 1## {-# INLINE (*%) #-} (/%) :: Int -> Int -> Int (/%) (I# x#) (I# y#) = go# y# MOD# 1# 0# where go# a# b# u# v# | isTrue# (b# ># 0#) = case a# `quotInt#` b# of q# -> go# b# (a# -# (q# *# b#)) v# (u# -# (q# *# v#)) | otherwise = I# ((x# *# (u# +# MOD#)) `remInt#` MOD#) {-# INLINE (/%) #-} (^%) :: Int -> Int -> Int (^%) x n | n > 0 = go 1 x n | n == 0 = 1 | otherwise = go 1 (1 /% x) (-n) where go !acc !y !m | m .&. 1 == 0 = go acc (y *% y) (unsafeShiftR m 1) | m == 1 = acc *% y | otherwise = go (acc *% y) (y *% y) (unsafeShiftR (m - 1) 1) newtype Mint = Mint { getMint :: Int } deriving newtype (Eq, Ord, Read, Show, Real) mint :: Integral a => a -> Mint mint x = fromIntegral $ mod (fromIntegral x) MOD {-# INLINE mint #-} instance Num Mint where (+) = coerce (+%) (-) = coerce (-%) (*) = coerce (*%) abs = id signum = const (Mint 1) fromInteger x = coerce @Int @Mint . fromInteger $ mod x modulus instance Bounded Mint where minBound = Mint 0 maxBound = Mint $ modulus - 1 instance Enum Mint where toEnum = mint fromEnum = coerce instance Integral Mint where quotRem x y = (x / y, x - x / y * y) toInteger = coerce (toInteger @Int) instance Fractional Mint where (/) = coerce (/%) fromRational q = fromInteger (numerator q) / fromInteger (denominator q) newtype instance VU.Vector Mint = V_Mint (VU.Vector Int) newtype instance VUM.MVector s Mint = MV_Mint (VUM.MVector s Int) instance VU.Unbox Mint instance VGM.MVector VUM.MVector Mint where basicLength (MV_Mint v) = VGM.basicLength v {-# INLINE basicLength #-} basicUnsafeSlice i n (MV_Mint v) = MV_Mint $ VGM.basicUnsafeSlice i n v {-# INLINE basicUnsafeSlice #-} basicOverlaps (MV_Mint v1) (MV_Mint v2) = VGM.basicOverlaps v1 v2 {-# INLINE basicOverlaps #-} basicUnsafeNew n = MV_Mint `fmap` VGM.basicUnsafeNew n {-# INLINE basicUnsafeNew #-} basicInitialize (MV_Mint v) = VGM.basicInitialize v {-# INLINE basicInitialize #-} basicUnsafeReplicate n x = MV_Mint `fmap` VGM.basicUnsafeReplicate n (coerce x) {-# INLINE basicUnsafeReplicate #-} basicUnsafeRead (MV_Mint v) i = coerce `fmap` VGM.basicUnsafeRead v i {-# INLINE basicUnsafeRead #-} basicUnsafeWrite (MV_Mint v) i x = VGM.basicUnsafeWrite v i (coerce x) {-# INLINE basicUnsafeWrite #-} basicClear (MV_Mint v) = VGM.basicClear v {-# INLINE basicClear #-} basicSet (MV_Mint v) x = VGM.basicSet v (coerce x) {-# INLINE basicSet #-} basicUnsafeCopy (MV_Mint v1) (MV_Mint v2) = VGM.basicUnsafeCopy v1 v2 {-# INLINE basicUnsafeCopy #-} basicUnsafeMove (MV_Mint v1) (MV_Mint v2) = VGM.basicUnsafeMove v1 v2 {-# INLINE basicUnsafeMove #-} basicUnsafeGrow (MV_Mint v) n = MV_Mint `fmap` VGM.basicUnsafeGrow v n {-# INLINE basicUnsafeGrow #-} instance VG.Vector VU.Vector Mint where basicUnsafeFreeze (MV_Mint v) = V_Mint `fmap` VG.basicUnsafeFreeze v {-# INLINE basicUnsafeFreeze #-} basicUnsafeThaw (V_Mint v) = MV_Mint `fmap` VG.basicUnsafeThaw v {-# INLINE basicUnsafeThaw #-} basicLength (V_Mint v) = VG.basicLength v {-# INLINE basicLength #-} basicUnsafeSlice i n (V_Mint v) = V_Mint $ VG.basicUnsafeSlice i n v {-# INLINE basicUnsafeSlice #-} basicUnsafeIndexM (V_Mint v) i = coerce `fmap` VG.basicUnsafeIndexM v i {-# INLINE basicUnsafeIndexM #-} basicUnsafeCopy (MV_Mint mv) (V_Mint v) = VG.basicUnsafeCopy mv v elemseq _ = seq {-# INLINE elemseq #-} ------------------------------------------------------------------------------- fact :: Int -> Mint fact = VU.unsafeIndex factCache {-# INLINE fact #-} recipFact :: Int -> Mint recipFact = VU.unsafeIndex recipFactCache {-# INLINE recipFact #-} nPk :: Int -> Int -> Mint nPk n k = fact n * recipFact (n - k) {-# INLINE nPk #-} nCk :: Int -> Int -> Mint nCk n k = fact n * recipFact (n - k) * recipFact k {-# INLINE nCk #-} _factCacheSize :: Int _factCacheSize = Fact_CACHE_SIZE {-# NOINLINE _factCacheSize #-} factCacheSize :: Int factCacheSize = min (modulus - 1) _factCacheSize {-# INLINE factCacheSize #-} factCache :: VU.Vector Mint factCache = VU.scanl' (\x y -> x * coerce y) (1 :: Mint) $ VU.generate factCacheSize (+1) {-# NOINLINE factCache #-} recipFactCache :: VU.Vector Mint recipFactCache = VU.scanr' ((*).coerce) (1 / factCache VU.! factCacheSize) $ VU.generate factCacheSize (+1) {-# NOINLINE recipFactCache #-} ------------------------------------------------------------------------------- logFactCacheSize :: Int logFactCacheSize = LOG_FACT_CACHE_SIZE {-# NOINLINE logFactCacheSize #-} logFactCache :: VU.Vector Double logFactCache = VU.scanl' (+) 0.0 $ VU.generate logFactCacheSize (log . fromIntegral . (+1)) {-# NOINLINE logFactCache #-} logFact :: Int -> Double logFact = VU.unsafeIndex logFactCache {-# INLINE logFact #-} lognPk :: Int -> Int -> Double lognPk n k = logFact n - logFact (n - k) {-# INLINE lognPk #-} lognCk :: Int -> Int -> Double lognCk n k = logFact n - logFact k - logFact (n - k) {-# INLINE lognCk #-} ------------------------------------------------------------------------------- main :: IO () main = do query <- readLn :: IO Int qs <- parseN3 query putStr . unlines . map (bool "Straight" "Flush") . VU.toList $ solver qs solver :: VU.Vector (Int, Int, Int) -> VU.Vector Bool solver = VU.map (\(n, m, k) -> (log (fromIntegral m) + lognCk n k) < ((log (fromIntegral (n - k + 1))) + ((fromIntegral k) * log (fromIntegral m))))