题目描述

The International Center for the Preservation of Ceramics (ICPC) is searching for motifs in some ancient mosaics. According to the ICPC's definition, a $\textit{mosaic}$ is a rectangular grid where each grid square contains a colored tile. A $\textit{motif}$ is similar to a mosaic but some of the grid squares can be empty. Figure G.1 shows an example motif and mosaic.

The rows of an $r_q \times c_q$ mosaic are numbered $1$ to $r_q$ from top to bottom, and the columns are numbered $1$ to $c_q$ from left to right.

A contiguous rectangular subgrid of the mosaic matches the motif if every tile of the motif matches the color of the corresponding tile of the subgrid. Formally, an $r_p \times c_p$ motif appears in an $r_q \times c_q$ mosaic at position ($r$, $c$) if for all $1 \leq i \leq r_p$, $1 \leq j \leq c_p$, the tile ($r+i-1$, $c+j-1$) exists in the mosaic and either the square ($i$, $j$) in the motif is empty or the tile at ($i$, $j$) in the motif has the same color as the tile at ($r+i-1$, $c+j-1$) in the mosaic.

Given the full motif and mosaic, find all occurrences of the motif in the mosaic.

Figure G.1: Motif (left) and mosaic (right) of Sample Input 1.

输入格式

The first line of input contains two integers $r_p$ and $c_p$, where $r_p$ and $c_p$ ($1 \leq r_p, c_p \leq 1000$) are the number of rows and columns in the motif. Then $r_p$ lines follow, each with $c_p$ integers in the range $[0, 100]$, denoting the color of the motif at that position. A value of $0$ denotes an empty square.

The next line of input contains two integers $r_q$ and $c_q$ where $r_q$ and $c_q$ ($1 \leq r_q, c_q \leq 1000$) are the number of rows and columns in the mosaic. Then $r_q$ lines follow, each with $c_q$ integers in the range $[1, 100]$, denoting the color of the mosaic at that position.

输出格式

On the first line, output $k$, the total number of matches. Then output $k$ lines, each of the form $r c$ where $r$ is the row and $c$ is the column of the top left tile of the match. Sort matches by increasing $r$, breaking ties by increasing $c$.

题目大意

简要题意

给出两个矩阵, 其中第二个矩阵所有元素非 $0$.

定义第一个矩阵在第二个矩阵中的坐标 $(l, r)$ 处「出现」, 当且仅当存在一种方式任意修改第一个矩阵所有为 $0$ 的元素后, 第一个矩阵的左上角在第二个矩阵的对应位置坐标为 $(l, r)$ 时可以与第二个矩阵的一部分完全重合.

求第一个矩阵在第二个矩阵中所有「出现」的位置和总「出现」次数。

输入格式

第一行, 两个整数 $r_p, c_p$, 表示第一个矩阵的行数和列数.

接下来 $r_p$ 行, 每行 $c_p$ 个整数, 描述第一个矩阵.

接下来一行, 两个整数 $r_q, c_q$, 表示第二个矩阵的行数和列数.

接下来 $r_q$ 行，每行 $c_q$ 个整数, 描述第二个矩阵.

输出格式

第一行, 一个整数 $k$, 表示「出现」的总次数.

接下来 $k$ 行, 每行两个整数 $x, y$, 表示每一次「出现」的坐标. 如果有多个, 请以 $x$ 为第一关键字, $y$ 为第二关键字升序排序后输出。

2 2
1 0
0 1
3 4
1 2 1 2
2 1 1 1
2 2 1 3

3
1 1
1 3
2 2