<s> """<STR_LIT>""" <EOL> __author__ = '<STR_LIT>' <EOL> class Solution ( object ) : <EOL> def solve ( self , cipher ) : <EOL> """<STR_LIT>""" <EOL> matrix , pattern = cipher <EOL> R1 , C1 = len ( matrix ) , len ( matrix [ <NUM_LIT:0> ] ) <EOL> R2 , C2 = len ( pattern ) , len ( pattern [ <NUM_LIT:0> ] ) <EOL> dp = [ [ <NUM_LIT:0> for _ in xrange ( C1 + <NUM_LIT:1> ) ] for _ in xrange ( R1 + <NUM_LIT:1> ) ] <EOL> for i in xrange ( <NUM_LIT:1> , R1 + <NUM_LIT:1> ) : <EOL> for j in xrange ( <NUM_LIT:1> , C1 + <NUM_LIT:1> ) : <EOL> dp [ i ] [ j ] = dp [ i - <NUM_LIT:1> ] [ j ] + dp [ i ] [ j - <NUM_LIT:1> ] - dp [ i - <NUM_LIT:1> ] [ j - <NUM_LIT:1> ] + matrix [ i - <NUM_LIT:1> ] [ j - <NUM_LIT:1> ] <EOL> pattern_sum = sum ( [ sum ( pattern [ i ] ) for i in xrange ( R2 ) ] ) <EOL> for i in xrange ( R1 - R2 + <NUM_LIT:1> ) : <EOL> for j in xrange ( C1 - C2 + <NUM_LIT:1> ) : <EOL> bottom = i + R2 <EOL> left = j + C2 <EOL> candidate_sum = dp [ bottom ] [ left ] - dp [ bottom ] [ j ] - dp [ i ] [ left ] + dp [ i ] [ j ] <EOL> if candidate_sum == pattern_sum : <EOL> matched = True <EOL> for a in xrange ( R2 ) : <EOL> for b in xrange ( C2 ) : <EOL> if matrix [ i + a ] [ j + b ] != pattern [ a ] [ b ] : <EOL> matched = False <EOL> break <EOL> if not matched : <EOL> break <EOL> if matched : <EOL> return "<STR_LIT>" <EOL> return "<STR_LIT>" <EOL> if __name__ == "<STR_LIT:__main__>" : <EOL> import sys <EOL> f = open ( "<STR_LIT>" , "<STR_LIT:r>" ) <EOL> testcases = int ( f . readline ( ) . strip ( ) ) <EOL> for t in xrange ( testcases ) : <EOL> matrix = [ ] <EOL> pattern = [ ] <EOL> R , C = map ( int , f . readline ( ) . strip ( ) . split ( '<STR_LIT:U+0020>' ) ) <EOL> for i in xrange ( R ) : <EOL> matrix . append ( map ( int , list ( f . readline ( ) . strip ( ) ) ) ) <EOL> R , C = map ( int , f . readline ( ) . strip ( ) . split ( '<STR_LIT:U+0020>' ) ) <EOL> for i in xrange ( R ) : <EOL> pattern . append ( map ( int , list ( f . readline ( ) . strip ( ) ) ) ) <EOL> cipher = matrix , pattern <EOL> s = "<STR_LIT>" % ( Solution ( ) . solve ( cipher ) ) <EOL> print s , </s>
