1
4 4
1234
4321
9999
9999
2 2
12
21

func findMultipleIndexes(str, substr string) []int {
    var indices []int
    start := 0
    for {
        index := strings.Index(str[start:], substr)
        if index == -1 {
            break
        }
        indices = append(indices, start+index)
        start += index + 1
    }
    return indices
}
func Contains(M []int, Item int) bool{
    for _,v  := range M {
        if v == Item {
            return true
        }
    }
    
    return false
}
func gridSearch(G []string, P []string) string {
    // Write your code here
    const NO = "NO"
    const YES = "YES"

    if len(P) == 0 {
        return "NO"
    }

    row := -1
    // find the first line of patter match
    for i, v := range G {
        cols := findMultipleIndexes(v, P[0])
        for _, col := range cols {
            row = i
            // if next not lines available at the Group
            if row == -1 || col == -1 || len(G) < row+len(P) {

                // return NO
                continue
            }

            found := true
            // now check for next lines
            for j := row + 1; j < row+len(P); j++ {
                i := j - row
                ncols := findMultipleIndexes(G[j], P[i])
                if !Contains(ncols, col) {
                    found = false
                    break
                }
            }

            if found {
                return YES
            }
        }
    }

    return NO
}

import qualified Data.Matrix as M
import Data.Char (digitToInt)

nOfCompairason pattern mat = (r !! ((M.nrows pattern) - 1),c !! ((M.ncols pattern) - 1))
  where r = reverse [1..(M.nrows mat)]
        c = reverse [1..(M.ncols mat)]

-- this is nothing like a cross correlation but you get the idea
-- submatrix is O(1)
crossCorrelation :: (Eq a) => M.Matrix a -> M.Matrix a -> Bool
crossCorrelation mat ptrn = or $ map (\ (a,aa,b,bb) -> ptrn == M.submatrix a aa b bb mat) compair
  where (cr,cc) = nOfCompairason ptrn mat
        pr = M.nrows ptrn - 1
        pc = M.ncols ptrn - 1
        compair = [(a,a+pr,b,b+pc) | a <- [1..cr], b <- [1..cc]]

yesNo bool | bool      = "YES"
           | otherwise = "NO"

-- typechecking seems to fail with a fold so i had to make this function
strToIntList :: String -> [Int]
strToIntList []     = []
strToIntList (x:xs) = (digitToInt x) : (strToIntList xs)

-- there's probably a cuter way to write I/O but that's not the important thing here
action = do
  rc <- getLine
  mat <- sequence $ replicate (read $ head $ words rc) getLine
  prc <- getLine
  ptr <- sequence $ replicate (read $ head $ words prc) getLine
  let matrix = M.fromLists $ map strToIntList mat
      patter = M.fromLists $ map strToIntList ptr
      res = yesNo $ crossCorrelation matrix patter
  putStrLn res

main = do
  times <-getLine
  sequence $ replicate (read times) action

 public static boolean checkPattern(List<String> G, List<String> P, int start_i, int start_j){
        int R = G.size();
        int C = G.get(0).length();
        
        int r = P.size();
        int c = P.get(0).length();
        
        int end_i = start_i + (r-1);
        int end_j = start_j + (c-1);
        
        if(end_i >= R || end_j >= C)
          return false;
        
        for(int i = 0; i < r; i++)
          for(int j = 0; j < c; j++){
            char pattern_num = P.get(i).charAt(j);  
            char grid_num = G.get(i + start_i).charAt(j + start_j);
            if(grid_num != pattern_num) return false;
            }
        return true;
        }
    
    public static String gridSearch(List<String> G, List<String> P) {
        int R = G.size();
        int C = G.get(0).length();
        char first_pattern_num = P.get(0).charAt(0);
        
        for(int i = 0; i < R; i++)
          for(int j = 0; j < C; j++){
            char grid_num = G.get(i).charAt(j);
            if(grid_num == first_pattern_num && checkPattern(G,P,i,j) )
              return "YES";
            }
        return "NO";
        }

func gridSearch(G: [String], P: [String]) -> String {
    // Write your code here
    
    var pIndex: Int = 0
    var gIndex: Int = 0
    var prevIndex: Int = -1
    
    var set = Set<Character>()
    
    while(gIndex <= G.count - 1) {
        if let ranged = G[gIndex].range(of: P[pIndex], options: .regularExpression) {
            let index: Int = G[gIndex].distance(from: G[gIndex].startIndex, to: ranged.lowerBound)
                   
            if prevIndex != -1 && prevIndex != index { 
                let squeezed: String = G[gIndex - 1].filter{ set.insert($0).inserted }
                if squeezed.count != 1 {
                    pIndex = 0
                    prevIndex = -1
                    continue
                }
             }
            if pIndex == P.count - 1 { break } 
            if pIndex < P.count - 1 { pIndex += 1 } 
            if prevIndex == -1 { prevIndex = index }
            
        } else if (pIndex != 0) {
            pIndex = 0 
            continue 
        }

        gIndex += 1
    }
        
    return pIndex == P.count - 1 ? "YES" : "NO"
}