#K57947. Submatrix Search

    ID: 30533 Type: Default 1000ms 256MiB

Submatrix Search

You are given a matrix \(M\) of size \(n \times m\) and a smaller matrix \(P\) of size \(k \times l\). Your task is to determine whether \(P\) exists as a contiguous submatrix of \(M\). If it does, output the 0-indexed coordinates of the top-left corner of the submatrix in \(M\); otherwise, output \(-1 -1\).

Input Format:

  • The first line contains two integers \(n\) and \(m\) — the number of rows and columns of \(M\), respectively.
  • The next \(n\) lines each contain \(m\) integers representing the rows of \(M\).
  • The following line contains two integers \(k\) and \(l\) — the number of rows and columns of \(P\), respectively.
  • The next \(k\) lines each contain \(l\) integers representing the rows of \(P\).

Output Format:

  • If \(P\) is a submatrix of \(M\), output the row and column indices (separated by a space) of the top-left corner where \(P\) is found in \(M\).
  • If \(P\) is not found, output \(-1 -1\).

Note: Both matrices are 0-indexed. The dimensions of \(P\) will always be less than or equal to those of \(M\).

inputFormat

The first line contains two integers \(n\) and \(m\) (\(1 \leq n, m \leq 1000\)).\nThe next \(n\) lines contain \(m\) integers each, representing the matrix \(M\).\nThen, a line with two integers \(k\) and \(l\) (\(1 \leq k \leq n, 1 \leq l \leq m\)) is given, followed by \(k\) lines containing \(l\) integers each, representing matrix \(P\).

outputFormat

Output a single line with two integers separated by a space. If the submatrix \(P\) is found in \(M\), output its top-left coordinates (row and column) using 0-indexing. Otherwise, output \(-1 -1\).

## sample
4 4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
2 2
6 7
10 11
1 1

</p>