Description

The problem is as follows:

For any $n$-by-$n$ matrix, if for any selection of $n$ positions with no two in the same row or column, the sum of the values on those positions is always the same, then we call this matrix “clever.” Note that any matrix with $n = 1$ is clever. For example, the matrix:

1 2 3
4 5 6
7 8 9

is clever because $1+5+9=1+6+8=2+4+9=2+6+7=3+5+7=3+4+8=15$.

The matrix:

1 2
2 1

is not clever because $1+1 \neq 2+2$.

Now you are given an $n \times m$ matrix $M$ and $T$ queries. Each query asks whether a subsquare is clever.

Input Format

Read from standard input.

The first line contains three positive integers $n, m, T$.

The next $n$ lines each contain $m$ space-separated non-negative integers, representing the matrix $M$.

The next $T$ lines each contain three positive integers $x, y, k$, indicating the $k$-by-$k$ square whose top-left corner is at row $x$, column $y$. It is guaranteed that this square lies entirely within $M$.

Output Format

Output to standard output.

Print $T$ lines, each containing a single character Y or N. Y means the queried square is clever, and N means it is not.

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

Y
N
N
Y

Hint

Constraints: For all the testdata, $0 \leq M_{ij} \leq 10^9$, $1 \leq x \leq n$, $1 \leq y \leq m$.

From CodePlus 2017 December Contest, proudly presented by the Student Association for Algorithms and Programming Contest, Department of Computer Science and Technology, Tsinghua University.

Credit: idea/卢政荣 命题/卢政荣 验题/吕时清，王聿中.

Git Repo: https://git.thusaac.org/publish/CodePlus201712

Thanks to Tencent for supporting this contest.

Translated by ChatGPT 5