{-# LANGUAGE BangPatterns #-}
import Control.Monad
import Data.Array
import Data.List
import Text.Printf
type Board = Array (Int,Int) Char
data Ans = Both | Blue | Red | Neither deriving Show
mkBoard :: Int -> [[Char]] -> Board
mkBoard n zss = array ((1,1),(n,n)) [((x,y),z) | (y,zs) <- zip [n,n-1..1] zss, (x,z) <- zip [1..n] zs ]
rotate :: Board -> Board
rotate board = ixmap (bounds board) (\(x,y) -> (n-y+1,x)) board
where ((_,_),(n,_)) = bounds board
gravity :: Board -> Board
gravity board = array (bounds board) $ do
x <- [1..n]
let f :: Int -> Int -> Int -> [(Int, Char)]
f !x !y !y'
| y > n = []
| y' > n = (y,'.') : f x (y+1) y'
| otherwise =
case board ! (x,y') of
'.' -> f x y (y'+1)
c -> (y, c) : f x (y+1) (y'+1)
(y,z) <- f x 1 1
return ((x,y), z)
where ((_,_),(n,_)) = bounds board
isWin :: Char -> Int -> Board -> Bool
isWin c k board = or $ do
xs <- xss
ys <- tails xs
return $ take k ys == replicate k c
where
((_,_),(n,_)) = bounds board
xss :: [String]
xss = map (map (board !)) (pss n)
pss :: Int -> [[(Int,Int)]]
pss n = [[(x,y) | y<-[1..n]] | x<-[1..n]] ++
[[(x,y) | x<-[1..n]] | y<-[1..n]] ++
[zip [x0..n] [1..n] | x0<-[1..n]] ++
[zip [1..n] [y0..n] | y0<-[2..n]] ++
[zip [x0..n] [n,n-1..] | x0<-[1..n]] ++
[zip [1..n] [y0,y0-1..1] | y0<-[1..n-1]]
f :: Int -> Board -> Ans
f k board
| b && r = Both
| b = Blue
| r = Red
| otherwise = Neither
where
b = isWin 'B' k board
r = isWin 'R' k board
main :: IO ()
main = do
t <- readLn
forM_ [(1::Int)..t] $ \x -> do
[n,k] <- liftM (map read . words) getLine
xss <- replicateM n getLine
let board = mkBoard n xss
board1 = rotate board
board2 = gravity board1
printf "Case #%d: %s\n" x (show (f k board2))